取水

题目描述

Famer John希望把水源引入他的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)。请你求出Farmer John最少要花多少钱才能够让他的所有牧场都有水源。

输入

* 第1行: 一个正整数N.
* 第2～N+1行: 第i+1行包含一个正整数W_i.
* 第N+2～2N+1行: 第N+1+i行包含N个用空格分隔的正整数,第j个数表示P_ij.

输出

最少要花多少钱才能够让他的所有牧场都有水源。

样例输入

0 2 2 2

2 0 3 3

2 3 0 4

2 3 4 0

样例输出

提示

输入数据解释总共有四个牧场.在1号牧场打一口井需要5的费用,在2或者3号牧场打井需要4的费用,在4号牧场打井需要3的费用.在不同的牧场间建立管道需要2,3或4的费用.

输出数据解释 Farmer John需要在4号牧场打一口井,然后把所有牧场都用管道连到1号牧场上,总共的花费是3+2+2+2=9.

对于30%的数据N<=10
对于60%的数据N<=100
对于100%的数据N<=300

这一道题目题目大意就是给你N个点的无向完全图，然后，每一个点都要有水源。这里我们可以设置一个超级源0，我们可以想象打井就相当于和这个0点连一条边。虽然小Z推荐了Prim做法，因为这是一个完全图。但是，由于我比较懒，所以我依然用了Kruskal。。。

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <iostream>
 5 #include <algorithm>
 6 
 7 using namespace std;
 8 
 9 struct node
10 {
11     int u,v,cost;    
12 };
13 
14 
15 node a[100005];
16 int f[100005];
17 int N;
18 int Len=0;
19 
20 bool cmp(node i,node j)
21 {
22     return i.cost < j.cost;
23 }
24 
25 int find(int X)
26 {
27     if (f[X] != X) f[X]=find(f[X]);
28     return f[X];
29 }
30 
31 int main()
32 {
33     scanf("%d",&N);
34     for (int i=1; i<=N; i++)
35     {
36         int X;
37         scanf("%d",&X);
38         a[++Len].u=0; a[Len].v=i; a[Len].cost=X;
39         f[i]=i;
40     }
41     for (int i=1; i<=N; i++)
42     {
43         for (int j=1; j<=N; j++)
44         {
45             int X;
46             scanf("%d",&X);
47             if (i == j) continue;
48             a[++Len].u=i; a[Len].v=j; a[Len].cost=X;
49         }
50     }
51     int ans=0; int total=0;
52     sort(a+1,a+Len+1,cmp);
53     for (int i=1; i<=Len; i++)
54     {
55         int fx=find(a[i].u);
56         int fy=find(a[i].v);
57         if (fx > fy) swap(fx,fy);
58         if (fx == fy) continue;
59         if (fx != fy)
60         {
61             f[fy]=fx;
62             ans+=a[i].cost;
63             total++;
64             if (total == N) break;
65         }
66     }
67     printf("%d\n",ans);
68 }

Show My Ugly Code