灌溉

 

【问题描述】

Farmer John 有𝑛个牧场，他希望灌溉他的所有牧场。牧场编号为1 ∼ 𝑛，要灌溉一个牧场有两种方式，一个是直接在这个牧场建设一个小型水库，另一个是从别的牧场向这个牧场引水。在第𝑖个牧场建立小型水库需要𝑊_{%美元，而从第𝑖 个}

牧场向第𝑗个牧场引水需要𝑃_{%,<美元。即便牧场𝑗没有建设小型水库，只要有别的有}

水的水库向它引水，那它自己也有水，而且可以向别的水库引水。请告诉 FJ 灌溉所有牧场所需的最小代价。

【输入格式】

输入数据的第一行包含一个整数𝑛，代表牧场的数目。

接下来𝑛行，每行包含一个整数𝑊_{%，代表建立小型水库的代价。接下来𝑛行，每行包含𝑛个整数。第𝑖行的第𝑗个数为𝑃%,<。}

【输出格式】

输出一行，包含一个整数，即为答案。

【样例】

irrigate.in	irrigate.out
4	9
5
4
4
3
0 2 2 2
2 0 3 3
2 3 0 4
2 3 4 0

【样例解释】

FJ 应该在第 4 块牧场上建立小型水库，然后从这块牧场向其他所有牧场引水。总费用为3 + 2 + 2 + 2 = 9美元。

【数据规模和约定】

对于 20%的数据，𝑛 ≤ 10。

对于 40%的数据，𝑛 ≤ 50。对于 60%的数据，𝑛 ≤ 100。

对于 100%的数据，1 ≤ 𝑛 ≤ 300，1 ≤ 𝑃_%,<, 𝑊_% ≤ 10>，𝑃_%,< = 𝑃_{<,%，𝑃%,%} = 0。

这个题如果不考虑自己建水库的情况，那么就是找一个最小生成树的模板问题，二而且n比较小，所以prim就可以解决。

那如果加上建水库的情况，本来考虑在比较的时候加上一个建水库的比较，但是只能过一半的点。

然后想了很久，如果在比较的时候加上建水库的情况的话，那么前面取进行更新的点时，就不能保证取到的点时最有的那一个。

然后就懵逼的没思路了。。。。。。

然后同桌说了一个很精辟的思路，将dis数组赋值为建水库的花费，突然感到很有道理，我们没有必要非得建成一棵树，我们可以先将每一个点都看做一棵树，那么如果这个点与别的点组成树比自己成为一棵树要优的话，那么就不将其加入到树中，但是这与将其加入树中的影响是相同的，只不过ans加的是其建成水站的费用，而不是与另外的点连接的花费。然后就愉快的结束了。

附上代码

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 int n,a[310][310],s[310],dis[310],vis[310],Min=0x7fffffff,ans;
 6 bool bz=0;
 7 int main()
 8 {
 9     scanf("%d",&n);
10     for(int i=1;i<=n;++i)
11     {
12         scanf("%d",&dis[i]);
13     }
14     for(int i=1;i<=n;++i)
15     {
16         for(int j=1;j<=n;++j)
17         {
18             scanf("%d",&a[i][j]);
19         }
20     }
21     dis[0]=0x7ffffff;
22     for(int i=1;i<n;++i)
23     {
24         int k=0;
25         for(int j=1;j<=n;++j)
26         {
27             if(!vis[j]&&dis[j]<dis[k])
28             {
29                 k=j;
30             }
31         }
32         vis[k]=1;
33         for(int j=1;j<=n;++j)
34         {
35             if(!vis[j])
36             dis[j]=min(dis[j],a[k][j]);
37         }
38     }
39     for(int i=1;i<=n;++i)
40     {
41         ans+=dis[i];
42     }
43     printf("%d",ans);
44     return 0;
45 }