題目描述

?

Farmer John已經決定把水灌到他的n(1<=n<=300)塊農田，農田被數字1到n標記。把一塊土地進行灌水有兩種方法，從其他農田飲水，或者這塊土地建造水庫。 建造一個水庫需要花費wi(1<=wi<=100000),連接兩塊土地需要花費Pij(1<=pij<=100000,pij=pji,pii=0). 計算Farmer John所需的最少代價。

?

---

輸入格式

?

*第一行：一個數n

*第二行到第n+1行：第i+1行含有一個數wi

*第n+2行到第2n+1行：第n+1+i行有n個被空格分開的數，第j個數代表pij。

?

---

輸出格式

?

*第一行：一個單獨的數代表最小代價.

?

---

樣例輸入

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

---

樣例輸出

9輸出詳解：Farmer John在第四塊土地上建立水庫，然后把其他的都連向那一個，這樣就要花費3+2+2+2=9

這道題是要把所有的點連在一起，也就是要用最小生成樹。直接用kruskal跑一遍就好了。 #include<algorithm> #include<cstdio> #include<cmath> #include<iostream> #include<cstring> using namespace std; const int maxn = 100005; int n; struct edge {int x, y, val; } e[maxn]; int ans, fa[305], t, cnt; int cmp(const edge &a, const edge &b) {return a.val < b.val; } int find(int x) {if(fa[x] != x)fa[x] = find(fa[x]);return fa[x]; } void get(int x, int y, int w) {cnt++;e[cnt].x = x;e[cnt].y = y;e[cnt].val = w; } int main() {scanf("%d", &n);for(int i = 1; i <= n; i++) {fa[i] = i;scanf("%d", &t);get(0,i,t);}for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++) {scanf("%d", &t);if(i != j) {get(i,j,t);}}sort(e + 1,e + cnt + 1,cmp);for(int i = 1; i <= cnt; i++) {if(find(e[i].x) != find(e[i].y)) {fa[find(e[i].x)] = find(e[i].y);ans += e[i].val;}}printf("%d\n", ans);return 0; } View Code

?

轉載于:https://www.cnblogs.com/jiqimin/p/10914231.html

總結

以上是生活随笔為你收集整理的[Usaco2008 Oct]灌水的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。