Description

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

Input

*第一行：一個(gè)數(shù)n

*第二行到第n+1行：第i+1行含有一個(gè)數(shù)wi

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

Output

*第一行：一個(gè)單獨(dú)的數(shù)代表最小代價(jià).

Sample Input

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

Sample Output

9


輸出詳解：

Farmer John在第四塊土地上建立水庫，然后把其他的都連向那一個(gè)，這樣就要花費(fèi)3+2+2+2=9

先構(gòu)造一個(gè)0號點(diǎn)表示水庫，Kruskal跑一遍最小生成樹就行。

#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; struct node{int x,y,c; }dat[100000]; int n,cnt,sum,ans; int map[301][301]; int fa[100000]; void insert(int u,int v,int w) {dat[++cnt].x=u;dat[cnt].y=v;dat[cnt].c=w;} int getfather(int x) {if (fa[x]==x) return x;fa[x]=getfather(fa[x]);return fa[x]; } bool cmp(node a,node b) {return a.c<b.c;} int main() {scanf("%d",&n);for (int i=1;i<=n;i++){int x;scanf("%d",&x);if (x!=0) insert(0,i,x);}for (int i=1;i<=n;i++)for (int j=1;j<=n;j++){int x;scanf("%d",&x);if (i<j) insert(i,j,x);}sort(dat+1,dat+cnt+1,cmp);for (int i=0;i<=n;i++) fa[i]=i;for (int i=1;i<=cnt;i++){int x=dat[i].x;int y=dat[i].y;int fx=getfather(x);int fy=getfather(y);if (fx!=fy){fa[fy]=fx;ans+=dat[i].c;sum++;} if (sum==n) break;}cout<<ans;return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/zhber/p/4035979.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。