POJ 1861 Network (Kruskal算法)

这道题目其实是最小生成树的题目。

但是题目给的样例有误导嫌疑，所以可能比较难的看出来。

一开始读题目，看样例，看了很久，怎么对也好样例不一样。

后面只好仔细在看一遍题目。发现题目讲的是，把任意两个点连通起来。

那么这个就是最小生成树的定义。

于是就按照最小生成树的样子写了一下。最后过了

证明确实题目给的样例确实是错的。

好好读题目才是关键

最后输出的是，最小生成树最长边，边数，以及每一条边

#include<iostream>
#include<algorithm>
#include<functional>
#include<cstdio>
#include<cstring>
#define maxn 150005
using namespace std;
struct node
{
	int from,to,cost;
}edge[maxn];
int n,m,fa[10005];
int k,ans[maxn];
int mx,cnt;
int cmp(struct node a,struct node b){return a.cost<b.cost;}//结构体从小到大排序
void init()//并查集初始化
{
	memset(edge,0,sizeof(edge));
	memset(ans,0,sizeof(ans));
	k=1;
	cnt=0;
	mx=-99999999;
	for(int i=1;i<=n;i++)
		fa[i]=i;
}
int getfa(int x)//找父亲节点
{
	if(x==fa[x])
		return x;
	return fa[x]=getfa(fa[x]);
}
int merge(int u,int v)//如果可以合并就合并，再返回1
{
	int t1,t2;
	t1=getfa(u);
	t2=getfa(v);
	if(t1!=t2)
	{
		fa[t1]=t2;
		return 1;
	}
	return 0;
}
int main()
{
	int i,j;
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		for(i=1;i<=m;i++)
			scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].cost);
		sort(edge+1,edge+m+1,cmp);//传的是地址
//		for(i=1;i<=m;i++)
//		printf("From:%d To:%d Cost:%d\n",edge[i].from,edge[i].to,edge[i].cost);

		for(i=1;i<=m;i++)
		{
//			printf("ans=%d\n",merge(edge[i].from,edge[i].to));
			if(merge(edge[i].from,edge[i].to))
			{
				mx=max(edge[i].cost,mx);
				ans[k++]=edge[i].from;
				ans[k++]=edge[i].to;
				cnt++;
			}
		}

		printf("%d\n",mx);
		printf("%d\n",cnt);
		for(i=1;i<k;i+=2)
			printf("%d %d\n",ans[i],ans[i+1]);
	}
	return 0;
}