描述

农夫约翰决定给他的N（1<=N<=300）个牧场浇水，这些牧场被自然的命名为1..N。他可以给一个牧场引入水通过在这个牧场挖一口井或者修一条管道使这个牧场和一个已经有水的牧场连接。

在牧场i挖一口井的花费是w_i（1<=w_i<=100000）。修建一条水管连接牧场i和牧场j的花费是p_ij（1<=p_ij<=100000;p_ij=p_ji;p_ii=0）。

请确定农夫约翰为了完成浇灌所有的牧场所需的最小的总花费。

题目名称：water

输入格式：

     第1行：一个单独的整数n。

第2..n+1行：第i+1行包含一个单独的整数w_i。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxn 123456789
 5 using namespace std;
 6 struct edge
 7 {
 8     int fr,to,w;
 9 }E[100000];//size > 300*300
10 int n,x,tot,num;
11 int w[302],father[302];
12 int find(int x)
13 {
14     if(father[x]!=x) father[x]=find(father[x]);
15     return father[x];
16 }
17 void unionn(int x,int y)
18 {
19     father[x]=y;
20 }
21 void add(int x,int y,int z)
22 {
23     num++;
24     E[num].fr=x;
25     E[num].to=y;
26     E[num].w=z;
27 }
28 bool cmp(const edge &a,const edge &b)
29 {
30     return a.w<b.w;
31 }
32 int main()
33 {
34     freopen("water.in","r",stdin);
35     freopen("water.out","w",stdout);
36     scanf("%d",&n);
37     for(int i=1;i<=n;i++)
38       father[i]=i;
39     for(int i=1;i<=n;i++)
40       scanf("%d",&w[i]);
41     for(int i=1;i<=n;i++)
42       for(int j=1;j<=n;j++)
43       {
44           scanf("%d",&x);
45         if(x)
46           add(i,j,x);
47       }
48     for(int i=1;i<=n;i++)
49     {
50         add(i,n+1,w[i]);//E2:从i向n+1(任一点)挖井的费用(把边存进去) 
51         add(n+1,i,w[i]);//E3:从n+1向i挖井的费用 E2的反图 
52     }
53     sort(E+1,E+num+1,cmp);
54     int k=0;
55     for(int i=1;i<=num;i++)
56     {
57         int r1=find(E[i].fr);
58         int r2=find(E[i].to);
59         if(r1!=r2)
60         {
61             unionn(r1,r2);
62             k++;
63             tot+=E[i].w;
64         }
65         if(k==n)//最小生成树的n-1条边+至少一个水井 
66           break;
67     }
68     printf("%d",tot);    
69     fclose(stdin);fclose(stdout);
70     return 0;
71 }