描述 Description
Farmer John 已经决定把水灌到他的 n(1<=n<=300) 块农田，农田被数字 1 到 n 标记。把一块土地进行灌水有两种方法，从其他农田饮水，或者这块土地建造水库。 建造一个水库需要花费 wi(1<=wi<=100000), 连接两块土地需要花费 Pij(1<=pij<=100000,pij=pji,pii=0). 计算 Farmer John 所需的最少代价。
输入格式 InputFormat
第一行：一个数 n.
第二行到第 n+1 行：第 i+1 行含有一个数 wi.
第 n+2 行到第 2n+1 行：第 n+1+i 行有 n 个被空格分开的数，第 j 个数代表 pij。
输出格式 OutputFormat
第一行：一个单独的数代表最小代价.
样例输入 SampleInput
10
537
914
269
536
882
245
172
615
367
688
0 56 91 16 53 82 30 52 51 51
56 0 36 24 12 41 67 50 37 99
91 36 0 96 6 34 2 60 74 58
16 24 96 0 25 27 8 79 34 14
53 12 6 25 0 12 23 30 44 7
82 41 34 27 12 0 79 68 87 66
30 67 2 8 23 79 0 39 32 14
52 50 60 79 30 68 39 0 57 38
51 37 74 34 44 87 32 57 0 1
51 99 58 14 7 66 14 38 1 0
样例输出 SampleOutput
266
来源 Source
资格赛
代码 Code
添加虚拟点 0 与每块土地连边，权值为该块土地建造水库的费用。跑一边 MST 即可。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct path
{
int z,y,x;
}a[100000];
int fa[305];
int i,j,t,n,m,l,r,k,ans;
bool comp(path a,path b)
{
return a.z<b.z;
}
int getfa(int s)
{
if (fa[s]==s) return s;
else fa[s]=getfa(fa[s]);
return fa[s];
}
void mst()
{
int i,j,t;
sort(a+1,a+m+1,comp);
for (i=1;i<=m;i++) if (getfa(a[i].x)!=getfa(a[i].y))
{
ans+=a[i].z;
fa[getfa(a[i].x)]=a[i].y;
}
}
int main()
{
scanf("%d",&n);
m=0;
for (i=0;i<=n;i++) fa[i]=i;
for (i=1;i<=n;i++)
{
scanf("%d",&t);
a[++m].x=0;a[m].y=i;a[m].z=t;
}
for (i=1;i<=n;i++) for (j=1;j<=n;j++)
{
scanf("%d",&t);
if (i<j)
{
a[++m].x=i;a[m].y=j;a[m].z=t;
}
}
ans=0;
mst();
printf("%d\n",ans);
return 0;
}