10
13
2015
0

[BZOJ1601] [Usaco2008 Oct] 灌水

加上一个点跑最小生成树即可。

#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;
}
Category: BZOJ | Tags: BZOJ | Read Count: 466

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com