185. [USACO Oct08] 挖水井

★★ 输入文件：water.in 输出文件：water.out 简单对比
时间限制：1 s 内存限制：128 MB

农夫约翰决定给他的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。
第n+2..2n+1行：第n+1+i行包含n个用空可分开的整数；其中第j个数是p_ij。

输入样例（file water.in）：

输入说明：

这里有4个牧场，修井和修管道的代价如图。

输出格式：

第1行：一个单独的整数，表示花费。

输出样例（file water.out）：

输出说明：

农夫约翰可以在第4个牧场修井，并且将每个牧场和第一个连接起来，这样，花费是3+2+2+2=9。

思路：另设一点，设此点到其他点的距离为最那些点挖井的费用，然后用最小生成树的算法。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 #define N 1010
 5 int far[N];
 6 int w[N];
 7 int n,m;
 8 long long ans,ct;
 9 int p;
10 struct node{
11     int a,b,c;
12 }famm[100000];
13 bool cmp(node x,node y)
14 {
15     return x.c<y.c;
16 }
17 int find(int a)
18 {
19     if(a!=far[a])far[a]=find(far[a]);
20     return far[a];
21 }
22 int main()
23 {
24     freopen("water.in","r",stdin);
25     freopen("water.out","w",stdout);
26     scanf("%d",&n);
27     for(int i=1;i<=n;++i)far[i]=i;
28     for(int i=1;i<=n;++i)
29     {
30         scanf("%d",&w[i]);
31     }
32     for(int i=1;i<=n;++i)
33     {
34         for(int j=1;j<=n;++j)
35         {
36             int x;
37             scanf("%d",&x);
38             if(x!=0)
39             {
40                 famm[++p].a=i;
41                 famm[p].b=j;
42                 famm[p].c=x;
43             }
44         }
45     }
46     for (int i=1;i<=n;++i)  
47     {  
48         p++;  
49         famm[p].a=i;  
50         famm[p].b=n+1;  
51         famm[p].c=w[i];  
52         p++;  
53         famm[p].a=n+1;  
54         famm[p].b=i;  
55         famm[p].c=w[i];  
56     }  
57     sort(famm+1,famm+p+1,cmp);    
58     for(int i=1;i<=p;++i)
59     {
60         int r=find(famm[i].a);
61         int rr=find(famm[i].b);
62         if(r!=rr)
63         {
64             far[rr]=r;
65             ans+=famm[i].c;
66             ++ct;    
67         }
68         if(ct==n)break;
69     }
70     printf("%lld",ans);
71     return 0;
72 }