加上一个点跑最小生成树即可。
#include<cstdio>
#include<cstdlib>
int en,f[305],n,a[305][305];
struct Edge{
int a,b,v;
}e[90005];
int cmp(const void *a,const void *b){
return (*(Edge *)a).v-(*(Edge *)b).v;
}
void add(int sa,int sb,int sc){
e[++en].a=sa;
e[en].b=sb;
e[en].v=sc;
}
int Find(int x){return x==f[x]?x:f[x]=Find(f[x]);}
void Union(int sa,int sb){
if(sa>sb)f[sa]=sb;
else f[sb]=sa;
}
int main(){
freopen("1601.in","r",stdin);
freopen("1601.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++){
int w;
f[i]=i;
scanf("%d",&w);
add(n+1,i,w);
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
add(i,j,a[i][j]);
}
}
qsort(e+1,en,sizeof(Edge),cmp);
int num=0,cost=0;
for(int i=1;i<=en;i++){
if(num==n)break;
if(Find(e[i].a)!=Find(e[i].b)){num++;e[i].a=Find(e[i].a);e[i].b=Find(e[i].b);Union(e[i].a,e[i].b);cost+=e[i].v;}
}
printf("%d\n",cost);
return 0;
}
评论 (0)
