211
poj 1861 Network MST
期末后第一次写题，结果就是这么灵异的一题……
样例是错的，这题实际上就是求个最小生成树，spj
/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define INF 1E9
using namespace std;
struct edge
{
int f,t,v;
};
bool cmp(edge a,edge b)
{
return a.v<b.v;
}
edge e[15005];
int fa[1005];
int far(int nn)
{
if(fa[nn]<0)return nn;
return fa[nn]=far(fa[nn]);
}
int main()
{
memset(fa,-1,sizeof(fa));
int n,m,f,t,v;
scanf("%d%d",&n,&m);
int i;
for(i=0;i<m;i++)
scanf("%d%d%d",&e[i].f,&e[i].t,&e[i].v);
sort(e,e+m,cmp);
int now,k,Max;
int ans[1000];
for(k=Max=0,now=1;now<n;k++)
{
f=far(e[k].f);t=far(e[k].t);
if(f==t)continue;
Max=max(Max,e[k].v);
if(fa[f]<fa[t])//加权法则，避免退化
{
fa[f]+=fa[t];
fa[t]=f;
}
else
{
fa[t]+=fa[f];
fa[f]=t;
}
ans[now]=k;
now++;
}
printf("%d\n",Max);
printf("%d\n",now-1);
for(i=1;i<now;i++)
printf("%d %d\n",e[ans[i]].f,e[ans[i]].t);
}
最后更新：2017-04-04 07:03:42