題目大意：有一塊地，分成nxm塊。有的塊上長著草，有的塊上是荒地。將任何一塊長著草的塊上的草拔掉都需要花費d個力氣，往任何一塊荒地上種上草都需要花費f個力氣，在草和荒地之間架一個籬笆需要花費b個力氣，如果一塊草地四周都是荒地，則得花掉4b個力氣。現(xiàn)在，要求最外一圈都種上草，草地與荒地之間要用籬笆隔開，最少需要花費多少個力氣？

題目分析：有籬笆要把草地和荒地隔開意味著把所有的塊分成兩個“陣營”。增加源點和匯點，用源點s代表草地“陣營”頭領，匯點t代表荒地“陣營”頭領，在初始時，從s向所有的草地（在邊界處的除外）連一條弧，容量為d，表示該塊草地要背叛頭領s投奔敵人的代價；從所有的荒地向匯點連一條弧，容量為f，表示該塊荒地放棄頭領t的代價；對于任意一個塊u，向所有與它相鄰的v連一條弧，容量為b，表示u與v對立的代價。我們要做的就是用最少的代價這些塊分成兩個“陣營”，實際上就是求最小割。

?

CP：第一次用ISAP來寫網(wǎng)絡流。。。

?

代碼如下：

# include<iostream> # include<cstdio> # include<vector> # include<queue> # include<cstring> # include<iostream> using namespace std;const int INF=1<<30; const int maxn=2505;int n,m; char p[60][60];struct Edge {int fr,to,cap,fw;Edge(int fr,int to,int cap,int fw){this->fr=fr;this->to=to;this->cap=cap;this->fw=fw;} }; struct ISAP {vector<Edge>edges;vector<int>G[maxn];int d[maxn],gap[maxn],p[maxn];int n,s,t,vis[maxn],cur[maxn];void init(int n){this->n=n;edges.clear();for(int i=0;i<n;++i) G[i].clear();}void addEdge(int u,int v,int cap){edges.push_back(Edge(u,v,cap,0));edges.push_back(Edge(v,u,0,0));int m=edges.size();G[u].push_back(m-2);G[v].push_back(m-1);}void bfs(int u){memset(vis,0,sizeof(vis));d[u]=0;queue<int>q;q.push(u);vis[u]=1;while(!q.empty()){int x=q.front();q.pop();for(int i=0;i<G[x].size();++i){Edge &e=edges[G[x][i]];if(e.cap>0) continue;int v=edges[G[x][i]^1].fr;if(!vis[v]){vis[v]=1;d[v]=d[x]+1;q.push(v);}}}}int augment(){int a=INF;for(int u=t;u!=s;u=edges[p[u]].fr){Edge &e=edges[p[u]];a=min(a,e.cap-e.fw);}for(int u=t;u!=s;u=edges[p[u]].fr){edges[p[u]].fw+=a;edges[p[u]^1].fw-=a;}return a;}int maxFlow(int s,int t){this->s=s,this->t=t;bfs(t);int flow=0;memset(gap,0,sizeof(gap));for(int i=0;i<n;++i) ++gap[d[i]];memset(cur,0,sizeof(cur));int x=s;while(d[s]<n){if(x==t){flow+=augment();x=s;}int flag=false;for(int i=cur[x];i<G[x].size();++i){Edge &e=edges[G[x][i]];if(e.cap>e.fw&&d[x]==d[e.to]+1){flag=true;p[e.to]=G[x][i];cur[x]=i;x=e.to;break;}}if(!flag){int m=n-1;for(int i=0;i<G[x].size();++i){Edge &e=edges[G[x][i]];if(e.cap>e.fw) m=min(m,d[e.to]);}if((--gap[d[x]])==0) break;d[x]=m+1;++gap[d[x]];cur[x]=0;if(x!=s) x=edges[p[x]].fr;}}return flow;} }; ISAP solver;int d,f,b; int dd[4][2]={{-1,0},{1,0},{0,-1},{0,1}};bool ok(int x,int y) {return x>=1&&x<=n&&y>=1&&y<=m; }int main() {int T;scanf("%d",&T);while(T--){int cnt=0;scanf("%d%d",&m,&n);scanf("%d%d%d",&d,&f,&b);for(int i=1;i<=n;++i){scanf("%s",p[i]+1);if(p[i][1]=='.'){++cnt;p[i][1]='#';}if(m>1&&p[i][m]=='.'){++cnt;p[i][m]='#';}if(i==1||i==n)for(int j=1;j<=m;++j)if(p[i][j]=='.'){++cnt;p[i][j]='#';}}solver.init(n*m+2);for(int i=1;i<=n;++i){for(int j=1;j<=m;++j){for(int k=0;k<4;++k){int ni=i+dd[k][0],nj=j+dd[k][1];if(ok(ni,nj)) solver.addEdge((i-1)*m+j,(ni-1)*m+nj,b);}if(p[i][j]=='#'){if(i==1||i==n||j==1||j==m)solver.addEdge(0,(i-1)*m+j,INF);elsesolver.addEdge(0,(i-1)*m+j,d);}else{solver.addEdge((i-1)*m+j,n*m+1,f);}}}printf("%d\n",solver.maxFlow(0,n*m+1)+cnt*f);}return 0; }

　　

轉載于:https://www.cnblogs.com/20143605--pcx/p/5107954.html

總結

以上是生活随笔為你收集整理的UVA-1515 Pool construction （最小割）的全部內容，希望文章能夠幫你解決所遇到的問題。

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