MST問題。
以下是我的代碼：
#include<algorithm>
#include<cstdio>
using namespace std;
const int kMaxn(1007);
const int kMaxm(15007);
struct Edge
{
int u,v,w;
};
bool operator<(const Edge &a,const Edge &b)
{
return (a.w<b.w);
}
int n,m,f[kMaxn];
Edge e[kMaxm],ans[kMaxn];
int Getf(int x)
{
if(x==f[x])
return x;
f[x]=Getf(f[x]);
return f[x];
}
int main()
{
while(scanf("%d%d",&n,&m)==2)
{
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
sort(e+1,e+m+1);
for(int i=1,j=0;i<=m && j<n-1;i++)
{
int u(e[i].u),v(e[i].v),fu(Getf(u)),fv(Getf(v));
if(fu!=fv)
{
f[fu]=fv;
j++;
ans[j].u=u;
ans[j].v=v;
ans[j].w=e[i].w;
}
}
printf("%d\n",ans[n-1].w);
printf("%d\n",n-1);
for(int i=1;i<n;i++)
printf("%d %d\n",ans[i].u,ans[i].v);
}
return 0;
}
posted on 2011-07-31 09:44
lee1r 閱讀(247)
評論(0) 編輯 收藏 引用 所屬分類:
題目分類：圖論