取水

时间限制: 1 Sec 内存限制: 128 MB
提交: 92 解决: 70
[提交][状态][讨论版]

题目描述

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.

输出

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

样例输入

样例输出

提示

输入数据解释总共有四个牧场.在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

题解：（刚开始接触这道题应该是在2015年的暑假，当时浪的飞起，没有怎么认真听）这道题关键就在于水源，它至少要打一个井，这个就比较麻烦了。最暴力的做法当然是枚举在什么地方打井，这样是

2^n能不能过30%都不知道，因此要改进算算法。这时想到了一个比较好的算法，就是想象一个水源，已经打好水，如果打水井就是从原点引入水，这样吧打井的费用为该井与水源的边权，这样求一次最小生成树就可以了，保证了，有水源，因为绝对有边与水源相连，十分巧妙。

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

View Code