本文共 1830 字，大约阅读时间需要 6 分钟。

楼教主男人八题第二题，5W个叶子节点合并最小费用

最小权费和二叉树：GW算法

#include 
   
    #include 
    
     using namespace std;#define maxn 50050#define maxV 1000000001int S = 1;int L = 0;long long V[maxn];int LAST[maxn];int NEXT[maxn];int main(){    int n;    while(scanf("%d",&n)!=EOF && n){        memset(V,0,sizeof(V));        memset(LAST,0,sizeof(LAST));        memset(NEXT,0,sizeof(NEXT));        L = n;        S = 1;        for(int i=1;i<=L;i++){            scanf("%lld",&V[i]);            LAST[i] = i-1;            NEXT[i] = i+1;        }        NEXT[L] = 0;        V[0] = maxV;        V[L+1] = maxV;        long long ans = 0;        int st = S;        while(L>2){            int i = st;            while(i!=0){                int a = LAST[i];                int b = NEXT[i];                if(V[a] <= V[b]){                    V[a] += V[i];                    ans += V[a];                    NEXT[a] = b;                    LAST[b] = a;                    i = a;                    break;                }                i = NEXT[i];            }            L--;            int j = i;            while(j!=0){                int j_last = LAST[j];                if(V[j_last] >= V[i]){                    if(i==j) break;                    int a = LAST[i];                    int b = NEXT[i];                    NEXT[a] = b;                    LAST[b] = a;                    NEXT[i] = j;                    LAST[i] = j_last;                    LAST[j] = i;                    NEXT[j_last] = i;                    if(j_last == 0) S = i;                    break;                }                j = LAST[j];            }            for(int k=0;k<2;k++){                if(i==S) break;                i = LAST[i];            }            st = i;        }        if(L==2) printf("%lld\n",ans+V[S]+V[NEXT[S]]);        if(L==1) printf("0\n");    }    return 0;}
    
   

转载地址：http://jkwji.baihongyu.com/