1 /* 2     此题为：HDOJ 1233 + HDOJ 1232 3 */ 4 #include 
     
       5 #include 
      
        6 #include 
       
         7 #include 
        
          8 using namespace std; 9 10 const int MAX_N = 100 + 10;11 int pre[MAX_N];12 int tot;13 int sum;14 struct NODE15 {16     int x, y;17     int len;18 }node[MAX_N];19 20 int find(int root)21 {22     int son, tmp;23     son = root;24 25     while (root != pre[root])26     {27         root = pre[root];28     }29     while (son != root)30     {31         tmp = pre[son];32         pre[son] = root;33         son = tmp;34     }35 36     return root;37 }38 39 bool cmp(NODE a, NODE b)40 {41     return a.len < b.len;42 }43 44 int main(void)        //HDOJ 1863 畅通工程45 {46     //freopen ("inC.txt", "r", stdin);47     int n, m;        //n路， m村庄48 49     while (~scanf ("%d%d", &n, &m) && n)50     {51         tot = m - 1;52         for (int i=1; i<=m; ++i)53         {54             pre[i] = i;55         }56         for (int i=1; i<=n; ++i)57         {58             scanf ("%d%d%d", &node[i].x, &node[i].y, &node[i].len);59         }60         sort (node+1, node+1+n, cmp);61         sum = 0;62         for (int i=1; i<=n; ++i)63         {64             int a, b;65             a = find (node[i].x);66             b = find (node[i].y);67             if (a != b)68             {69                 pre[a] = b;70                 sum += node[i].len;71                 --tot;72             }73         }74         if (tot == 0)75             printf ("%d\n", sum);76         else77             puts ("?");78     }79 }