[kuangbin带你飞]专题六 最小生成树 POJ 2421 Constructing Roads

给一个n个点的完全图 再给你m条道路已经修好 问你还需要修多长的路才能让所有村子互通

将给的m个点的路重新加权值为零的边到边集里 然后求最小生成树

 #include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#define cl(a,b) memset(a,b,sizeof(a))
#define debug(x) cerr<<#x<<"=="<<(x)<<endl
using namespace std;
typedef long long ll; const int maxn=; int f[maxn],tol,n,m; struct _edge
{
int u,v,w;
}edge[maxn*maxn*maxn]; bool cmp(_edge a,_edge b)
{
return a.w<b.w;
} void addedge(int u,int v,int w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol].w=w;
tol++;
} int _find(int x)
{
if(f[x]==-) return x;
else return f[x]=_find(f[x]);
} int kruskal()
{
cl(f,-);
sort(edge,edge+tol,cmp);
int cnt=,ans=;
int u,v,w,f1,f2;
for(int i=; i<tol; i++)
{
u=edge[i].u;
v=edge[i].v;
w=edge[i].w;
f1=_find(u);
f2=_find(v);
if(f1!=f2)
{
ans+=w;
f[f1]=f2;
cnt++;
}
if(cnt==n-) break;
}
return ans;
} int main()
{
while(scanf("%d",&n)!=EOF&&n)
{
tol=;
for(int i=;i<n;i++)
{
for(int j=;j<n;j++)
{
int x;
scanf("%d",&x);
addedge(i,j,x);
}
}
scanf("%d",&m);
for(int i=;i<m;i++)
{
int x,y;
scanf("%d%d",&x,&y);
addedge(x-,y-,);
addedge(y-,x-,);
}
printf("%d\n",kruskal());
}
return ;
}
/* 3
0 990 692
990 0 179
692 179 0
1
1 2 */
上一篇:jQuery 对AMD的支持(Require.js中如何使用jQuery)


下一篇:springmvc基础篇—通过注解的方式去配置项目