程式碼備份區

題意：

有很多條路，每條路上會有路燈，每一公尺的路燈花費是1，求說要如何讓所有點都互相連的到，而且路燈花費最少

問說全部路燈都開減掉最少花費的值

解法：

做Minimum Spanning Tree，做完之後把總和扣掉做出來的值即可

將邊由小到大做排序，從小的慢慢收進來，直到收到n-1個為止
 

程式碼：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int e[500000][3];
int n,m;
int set[500000];

int cmp(const void*a,const void*b){
    int *p = (int*)a;
    int *q = (int*)b;
    return p[2]-q[2];
}
int findSet(int now){
    if(set[now]!=now)set[now] = findSet(set[now]);
    return set[now];
}
int main(){
    int i;
    int setA,setB;
    int ans;
    while(scanf("%d %d",&n,&m)!=EOF &&(n|m)){
        for(i=0;i<n;++i){
            set[i] = i;
        }
        for(i=ans=0;i<m;++i){
            scanf("%d %d %d",&e[i][0],&e[i][1],&e[i][2]);
            ans += e[i][2];
        }
        qsort(e,m,sizeof(e[0]),cmp);
        for(i=0;n>1;++i){
            setA = findSet(e[i][0]);
            setB = findSet(e[i][1]);
            if(setA !=setB){
                set[setA] = setB;
                ans -= e[i][2];
                --n;
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}