http://acm.hdu.edu.cn/showproblem.php?pid=4289

唉 本來對網絡流的題目就不是很擅長 而且最近也沒去碰這方面的題

結果這次有兩個用最大流的? 而且都是拆點的? 傷不起呀

這個題把每個點拆成兩個點 一個入點 一個出點?入點到出點流就為 所給費用 出點到入點流為 0?

對于相連的點 相互之間都是? I 點的出點到 J 點的入點流為最大 J 點的入點到 I 點的出點流為0

將 I 點和 J 點對換再建一次

最后Dinic

代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <queue> #include <algorithm>#define LL long long//#pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;const int N=405; const int M=200000; const int INF=0x3f3f3f3f; int head[N]; struct node {int j,next;int f; }side[M]; int I; int L[N]; //int a[N]; queue<int>str; int K; int s,t; void build(int i,int j,int f) {side[I].j=j;side[I].f=f;side[I].next=head[i];head[i]=I++; } int bfs() {memset(L,-1,sizeof(L));str.push(s);L[s]=0;while(!str.empty()){int x=str.front();str.pop();for(int t=head[x];t!=-1;t=side[t].next){int l=side[t].j;if(L[l]==-1&&side[t].f>0){L[l]=L[x]+1;str.push(l);}}}//cout<<L[K]<<endl;return L[K]; } int dfs(int x,int sum) {//cout<<sum<<endl;if(x==K)return sum;int temp=sum;for(int t=head[x];t!=-1;t=side[t].next){int l=side[t].j;if(L[x]+1==L[l]&&side[t].f>0){int w=dfs(l,min(temp,side[t].f));temp-=w;side[t].f-=w;side[t^1].f+=w;}if(temp==0)break;}//cout<<sum-temp<<endl;return (sum-temp); } int main() {//freopen("data.txt","r",stdin);int n,m;while(scanf("%d %d",&n,&m)!=EOF){scanf("%d %d",&s,&t);memset(head,-1,sizeof(head));I=0;for(int i=1;i<=n;++i){int a;scanf("%d",&a);build(i,i+n,a);build(i+n,i,0);}while(m--){int i,j;scanf("%d %d",&i,&j);build(i+n,j,INF);build(j,i+n,0);build(j+n,i,INF);build(i,j+n,0);}K=t+n;int ans=0;while(bfs()!=-1){int k;while(k=dfs(s,INF))ans+=k;}printf("%d\n",ans);}return 0; }

?

轉載于:https://www.cnblogs.com/liulangye/archive/2012/09/17/2689194.html

總結

以上是生活随笔為你收集整理的hdu 4289 Control的全部內容，希望文章能夠幫你解決所遇到的問題。

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