并查集。

1 #include 
     
       2 #include 
      
        3 #include 
       
         4  5 #define MAXN 10005 6 #define INF  0xffffff 7  8 typedef struct { 9     int c, s, e;10 } edge_st;11 12 edge_st edges[100005];13 int pre[MAXN];14 int deg[MAXN];15 int n, m, ans;16 17 int comp(const void *a, const void *b) {18     return ((edge_st *)b)->c - ((edge_st *)a)->c;19 }20 21 int find(int x) {22     return x==pre[x] ? x:pre[x]=find(pre[x]);23 }24 25 void merge(int i) {26     int a, b;27 28     a = find(edges[i].s);29     b = find(edges[i].e);30     if (a != b) {31         if (deg[a] == 0) {32             pre[a] = b;33             ans += edges[i].c;34         } else if (deg[b] == 0) {35             pre[b] = a;36             ans += edges[i].c;37         }38     } else {39         if (deg[a] == 0) {40             ++deg[a];41             ans += edges[i].c;42         }43     }44 }45 46 int main() {47     int i;48 49     while (scanf("%d %d", &n, &m)!=EOF && (n||m)) {50         for (i=0; i