TZOJ 2754 Watering Hole(最小生成树Kruskal)

描述

Farmer John has decided to bring water to his N (1 <= N <= 300) pastures which are conveniently numbered 1..N. He may bring water to a pasture either by building a well in that pasture or connecting the pasture via a pipe to another pasture which already has water.

Digging a well in pasture i costs W_i (1 <= W_i <= 100,000). Connecting pastures i and j with a pipe costs P_ij (1 <= P_ij <= 100,000; P_ij = P_ji; P_ii=0).

Determine the minimum amount Farmer John will have to pay to water all of his pastures.

输入

Line 1: A single integer: N
Lines 2..N + 1: Line i+1 contains a single integer: W_i
Lines N+2..2N+1: Line N+1+i contains N space-separated integers; the j-th integer is P_ij

输出

Line 1: A single line with a single integer that is the minimum cost of providing all the pastures with water.

样例输入

4
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

样例输出

提示

INPUT DETAILS:

There are four pastures. It costs 5 to build a well in pasture 1,4 in pastures 2 and 3, 3 in pasture 4. Pipes cost 2, 3, and 4depending on which pastures they connect.

OUTPUT DETAILS:

Farmer John may build a well in the fourth pasture and connect each pasture to the first, which costs 3 + 2 + 2 + 2 = 9.

题意

农夫要打若干井，和挖连通两个田的水路，求所有田都有水的最小花费

题解

由于有一个挖井系统且必须要挖1个井，所以可以把井看成1个图上的点，然后跑一遍最小生成树即可

代码

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 #define MAXN 300+5
 7 #define MAXM 90000
 8 int n,m,F[MAXN],Vis[MAXN];
 9 struct edge
10 {
11     int u,v,w;
12 }edges[MAXM];
13 int Find(int x)
14 {
15     return F[x]==-1?x:F[x]=Find(F[x]);
16 }
17 bool cmp(edge a,edge b)
18 {
19     return a.w<b.w;
20 }
21 int Kruskal()
22 {
23     memset(F,-1,sizeof(F));
24     sort(edges,edges+m,cmp);
25     int ans=0,cnt=0,u,v,w,fx,fy;
26     for(int i=0;i<m;i++)
27     {
28         u=edges[i].u;
29         v=edges[i].v;
30         w=edges[i].w;
31         fx=Find(u);
32         fy=Find(v);
33         if(fx!=fy)
34         {
35             ans+=w;
36             cnt++;
37             F[fx]=fy;
38         }
39         if(cnt==n)break;//连通田n-1条边，加井1条边
40     }
41     return ans;
42 }
43 void addedges(int u,int v,int w)
44 {
45     edges[m].u=u;
46     edges[m].v=v;
47     edges[m++].w=w;
48 }
49 int main()
50 {
51     int w;
52     scanf("%d",&n);
53     for(int i=1;i<=n;i++)
54     {
55         scanf("%d",&w);
56         addedges(0,i,w);
57     }
58     for(int i=1;i<=n;i++)
59     {
60         for(int j=1;j<=n;j++)
61         {
62             scanf("%d",&w);
63             if(i>=j)continue;
64             addedges(i,j,w);
65         }
66     }
67     int ans=Kruskal();
68     printf("%d
",ans);
69     return 0;
70 }