經(jīng)典延伸最小生成樹問題。。。

#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++) #define dwn(i,s,t) for(int i=s;i>=t;i--) #define clr(x,c) memset(x,c,sizeof(x)) int read(){int x=0;char c=getchar();while(!isdigit(c)) c=getchar();while(isdigit(c)) x=x*10+c-'0',c=getchar();return x; } const int nmax=305; const int maxn=100005; const int inf=0x7f7f7f7f; struct edge{int from,to,dist;bool operator<(const edge &rhs)const{return dist<rhs.dist;} }; edge es[maxn]; int fa[nmax]; int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]); } int main(){int n=read(),u,v,d,cnt=0;rep(i,1,n) {es[++cnt].from=i,es[cnt].to=n+1,es[cnt].dist=read();}rep(i,1,n) rep(j,1,n){u=read();if(i!=j) es[++cnt].from=i,es[cnt].to=j,es[cnt].dist=u;}sort(es+1,es+cnt+1);int ans=0,tot=0;rep(i,1,n+1) fa[i]=i;rep(i,1,cnt){int ta=find(es[i].from),tb=find(es[i].to);if(ta!=tb){fa[ta]=tb;ans+=es[i].dist;if(++tot==n) break;}}printf("%d\n",ans);return 0; }

　

1601: [Usaco2008 Oct]灌水

Time Limit:?5 Sec??Memory Limit:?162 MB
Submit:?1776??Solved:?1162
[Submit][Status][Discuss]

Description

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

Input

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

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

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

Output

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

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在第四塊土地上建立水庫，然后把其他的都連向那一個，這樣就要花費3+2+2+2=9

HINT

Source

資格賽

[Submit][Status][Discuss]

轉(zhuǎn)載于:https://www.cnblogs.com/fighting-to-the-end/p/5858164.html

總結(jié)

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

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