POJ 1861 Network

题意：有n个点，部分点之间可以连接无向边，每条可以连接的边都有一个权值。求一种连接方法将这些点连接成一个连通图，且所有连接了的边中权值最大的边权值最小。

解法：水题，直接用Kruskal算法做一遍就行了，不过还是应该仔细想想为什么Kruskal可行。原因是，在从小边往大边遍历的过程中(一直保持图为连通图)，若判定某边i必须被连接，则因为图是连通图，所以连接比它小的边不可能使边i不需要连接，所以，要使边i不需要连接，必须连接比它大的边，根据题目要求，还是连接边i情况更优。

tag：最小生成树

 /*

  * Author:  Plumrain

  * Created Time:  2013-11-24 20:57

  * File Name: G-POJ-1861.cpp

  */

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 #define CLR(x) memset(x, 0, sizeof(x))

 #define PB push_back

 const int maxm =  * ;

 const int maxn = ;

 struct pat{

     int s, t, l;

 };

 pat p[maxm];

 bool v[maxm];

 vector<int> ans;

 int n, m, all, f[maxn];

 bool cmp(pat a, pat b)

 {

     return a.l < b.l;

 }

 void init()

 {

     int t1, t2, t3;

     all = ;

     for (int i = ; i < m; ++ i){

         scanf ("%d%d%d", &t1, &t2, &t3);

         -- t1; -- t2;

         p[all].s = p[all+].t = t1;

         p[all].t = p[all+].s = t2;

         p[all++].l = t3;

         p[all++].l = t3;

     }

 }

 void Kruskal()

 {

     sort(p, p+all, cmp);

     for (int i = ; i < n; ++ i) f[i] = i;

     CLR (v);

     for (int i = ; i < all; ++ i){

         int t1 = p[i].s, t2 = p[i].t;

         while (t1 != f[t1]) t1 = f[t1];

         while (t2 != f[t2]) t2 = f[t2];

         if (t1 != t2){

             v[i] = ;

             f[t1] = t2;

         }

     }

 }

 int main()

 {

     while (scanf ("%d%d", &n, &m) != EOF){

         init();

         Kruskal();

         ans.clear();

         int cnt = ;

         for (int i = ; i < all; ++ i) if (v[i]){

             cnt = max(i, cnt);

             ans.PB(i);

         }

         int sz = ans.size();

         printf ("%d\n%d\n", p[cnt].l, sz);

         for (int i = ; i < sz; ++ i)

             printf ("%d %d\n", p[ans[i]].s+, p[ans[i]].t+);

     }

     return ;

 }