有一些模塊（modules）和一個雙核處理器，一個模塊可以在任意一個核上處理，每個核對應每個模塊有個開銷。現在有一些模塊間需要數據交換，如果需要數據交換的模塊在一個核上處理，則不需要額外開銷，否則需要加上一個開銷。現在需要完成所有模塊，問最小需要多少開銷。

如果沒有這個額外的開銷，那么每個模塊只要選擇開銷小的那個核就行了。額外的開銷給選擇加上了限制。

先講講我的錯誤思路：拿A,B兩臺機器分別作為源點和匯點，然后將n個模塊拆成兩個，即x->x'，這樣就形成了A->x->x'->B的模型了，拆開的x和x'之間賦無窮大，A->x和x'->B賦相應的花費即可，額外的開銷就是a->b'和b->a'賦值為w即可。最后跑最大流，結果WA。。參考了別人的思路，發現我的建圖有問題，因為x->x'之間賦了無窮大，說明這條邊是不起作用的，這條邊可以“穿梭自如”，很有可能A->x和x'->B都會被我們選中，所以WA也是自然而然的了。

看了別人的建圖，確實解決了這個問題，不需要拆點，直接就是A->x->B即可，再根據額外的開銷a->b和b->a建邊即可。

#include <iostream> #include <algorithm> #include <queue> #include <stack> #include <math.h> #include <stdio.h> #include <string.h> using namespace std; #define MOD 1000000007 #define maxn 20010 #define maxm 1000000 #define LL long long struct Eg{int to;int next;int f; }E[maxm]; int V[maxn],num; int N,M; void add(int u,int v,int c){E[num].to=v;E[num].f=c;E[num].next=V[u];V[u]=num++;E[num].to=u;E[num].f=0;E[num].next=V[v];V[v]=num++; } int level[maxn]; int qu[maxn]; bool BFS(int s,int t){int i,iq=0;for(i=0;i<=t;i++) level[i]=0;int u,v,e;qu[iq++]=s;level[s]=1;for(i=0;i<iq;i++){u=qu[i];if(u==t) return true;for(e=V[u];e!=-1;e=E[e].next){v=E[e].to;if(!level[v]&&E[e].f>0){level[v]=level[u]+1;qu[iq++]=v;}}}return false; } int cur[maxn]; int dfs(int u,int maxf,int t){if(u==t||maxf==0) return maxf;int ret=0,f,e,v;for(e=cur[u];e!=-1;e=E[e].next){// 當前弧優化v=E[e].to;if(E[e].f>0&&level[u]+1==level[v]){f= dfs(v,min(maxf,E[e].f),t);E[e].f-=f;E[e^1].f+=f;maxf-=f;ret+=f;cur[u]=e;if(maxf==0) break;}}return ret; } int Dinic(int s,int t){int flow=0;while(BFS(s,t)){for(int i=0;i<=t;i++)cur[i]=V[i];flow+=dfs(s,MOD,t);}return flow; } int main(){int i;int a,b,w;while(scanf("%d %d",&N,&M)!=EOF){for(i=0;i<=N+1;i++)V[i]=-1;num=0;for(i=1;i<=N;i++){scanf("%d %d",&a,&b);add(0,i,a);add(i,N+1,b);}while(M--){scanf("%d %d %d",&a,&b,&w);add(a,b,w);add(b,a,w);}printf("%d\n",Dinic(0,N+1));}return 0; }

總結

以上是生活随笔為你收集整理的poj 3469(最小割)的全部內容，希望文章能夠幫你解決所遇到的問題。

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