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