929
POJ 2421 最小生成樹
題意：給出每兩個城市間建路的花費和已經擁有的路，求最小花費讓圖連通。
最小生成樹。。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxv=105,maxe=10005;
struct node
{
int w,to,next,f;
} e[maxe];
int head[maxv],dis[maxv],p[maxv],edge,n;
void add(int u,int v,int c)
{
e[edge].f=v,e[edge].to=u,e[edge].w=c,e[edge].next=head[u],head[u]=edge++;
}
int cmp(node a,node b)
{
return a.w<b.w;
}
int find(int x)
{
return p[x]==x?x:p[x]=find(p[x]);
}
int kru()
{
int ans=0;
for(int i=0; i<n; i++) p[i]=i;
sort(e,e+edge,cmp);
for(int i=0; i<edge; i++)
{
int x=find(e[i].f),y=find(e[i].to);
if(x!=y)ans+=e[i].w,p[x]=y;
}
return ans;
}
int main()
{
int q,val;
while(~scanf("%d",&n))
{
edge=0;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
{
scanf("%d",&val);
if(i!=j)
add(i,j,val);
}
scanf("%d",&q);
for(int i=0; i<q; i++)
{
int u,v;
scanf("%d%d",&u,&v);
for(int j=0; j<edge; j++)
if((e[j].f==u-1&&e[j].to==v-1)||(e[j].f==v-1&&e[j].to==u-1))
e[j].w=0;
}
printf("%d\n",kru());
}
return 0;
}
最後更新：2017-04-03 16:48:57