POJ-3469- 一道标准的最小割问题

本文主要是介绍POJ-3469- 一道标准的最小割问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意略

链接：http://poj.org/problem?id=3469

建图方式：

> 将每个任务规约为一个点,添加源汇点s.t

  s和每个任务相连,边权为任务在s上处理用的时间;
> 每个任务和t相连,边权为任务在t上处理用的时间.对于(a,b,w),连两条边(a,b,w)和(b,a,w);
> 为什么最小割就是解呢?
> 由最小割的定义,点基被分成两部分S.T,S为源点能到达的点的集合,其余点构成T;
> 再来看此题,假如s和a之间的边是割,那么a在s上被处理,否则a在t上被处理,s能到达的点在t上处理,其余点在s上处理;

代码：

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 40050;
const int maxm = 1000050;
const int INF = 0x7FFFFFF;
typedef long long ll;
#define mem(name,value) memset((name),(value),sizeof(name))
struct Side{int to,next,c;
}side[maxm];
int top,node[maxn];
void add_side(int u,int v,int c,int rc){side[top]=(Side){v,node[u],c};node[u]=top++;side[top]=(Side){u,node[v],rc};node[v]=top++;
}
int start,end,cnt,dis[maxn],gap[maxn];
int get_flow(int u,int flow){//printf("%d %d\n",u,flow);if(u==end)return flow;int ans=0;for(int i=node[u];i!=-1;i=side[i].next){int v=side[i].to,c=side[i].c;if(dis[u]>dis[v]&&c){int f=get_flow(v,min(flow-ans,c));ans+=f;side[i].c-=f;side[i^1].c+=f;if(ans==flow)return ans;}}if(!(--gap[dis[u]]))dis[start]=cnt+2;gap[++dis[u]]++;return ans;
}
int main(){freopen("input.txt","r",stdin);int n,m,i;while(~scanf("%d%d",&n,&m)){top=0;mem(node,-1);mem(gap,0);mem(dis,0);for(i=1;i<=n;i++){int a,b;scanf("%d%d",&a,&b);add_side(0,i,a,0);add_side(i,n+1,b,0);}while(m--){int u,v,w;scanf("%d%d%d",&u,&v,&w);add_side(u,v,w,0);add_side(v,u,w,0);}int ans=0;start=0;end=n+1;cnt=n+2;gap[0]=cnt;while(dis[start]<cnt) ans+=get_flow(start,INF);printf("%d\n",ans);}return 0;
}

这篇关于POJ-3469- 一道标准的最小割问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---