今天刷一下水题练手入门，明天继续。
poj1861 Network（最小生成树）新手入门题。
题意：输出连接方案中最长的单根网线长度（必须使这个值是所有方案中最小的），然后输出方案。
题解：本题没有直接求生成树，但如果连接n个集线器的方案多于n-1条边，那么必存在回路，因此去掉某些边剩下的边和所有顶点构成一个生成树。对于一个图的最小生成树来说，它的最大边满足所有生成树的最大边里最小，正和题意。
吐槽：题目样例是错的。。。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=1001; 6 struct edge{ 7 int u,v,w; 8 }e[15001]; 9 int f[N],a[N],ai; 10 int n,m,ma; 11 int cmp(edge a,edge b){ 12 return a.w<b.w; 13 } 14 void init(){ 15 for(int i=1;i<=n;++i) 16 f[i]=i; 17 } 18 int fin(int x){ 19 if(x!=f[x])f[x]=fin(f[x]); 20 return f[x]; 21 } 22 void Kruskal(){ 23 ma=ai=0; 24 int u,v,i; 25 init(); 26 for(i=0;i<m;++i){ 27 u=e[i].u; 28 v=e[i].v; 29 if((u=fin(u))!=(v=fin(v))){ 30 f[u]=v; 31 a[ai++]=i; 32 ma=max(e[i].w,ma); 33 } 34 if(ai>=n-1)break; 35 } 36 } 37 int main(){ 38 int i,u,v,w; 39 scanf("%d%d",&n,&m); 40 for(i=0;i<m;++i){ 41 scanf("%d%d%d",&u,&v,&w); 42 e[i]=edge{u,v,w}; 43 } 44 sort(e,e+m,cmp); 45 Kruskal(); 46 printf("%d\n%d\n",ma,ai); 47 for(i=0;i<ai;++i) 48 printf("%d %d\n",e[a[i]].u,e[a[i]].v); 49 return 0; 50 }