首页 > 代码库 > sgu 194上下界网络流
sgu 194上下界网络流
又搞了个模板,这个模板应该ok,足以应付各种网络流了
题意:给n个点m 条边,其中每条边的流量有两个限制不能大于r不能小于l,求是否有可行解,如有输出每条边的流量
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1000000; const int oo = 0x3777777; struct arc{ int to,cap,flow,next; arc(int x = 0,int y=0,int z = 0,int u =0){ to = x;cap = y; flow = z;next = u; } }; arc e[maxn]; int head[maxn],d[maxn],tot,id[maxn],work[maxn]; int S,T,q[maxn],hd,tail,n,m; void add(int u,int v,int cap,int flow,int ID){ id[tot] = ID; e[tot] = arc(v,cap,flow,head[u]); head[u] = tot++; id[tot] = 0; e[tot] = arc(u,0,-flow,head[v]); head[v] = tot++; } bool bfs(){ for(int i=1;i<=T;i++) d[i] = 0; d[S] = 1; hd = tail = 0; q[tail++] = S; while(hd != tail){ int u = q[hd++]; if(hd == maxn)hd =0; for(int i=head[u];i!=-1;i=e[i].next){ if(e[i].cap > e[i].flow && !d[e[i].to]){ d[e[i].to] = d[u] + 1; q[tail++] = e[i].to; if(tail == maxn)tail = 0; if(T == e[i].to)return true; } } } return false; } int dfs(int u,int low){ int tmp = 0,f; if(u==T||!low)return low; for(int &i=work[u];i!=-1;i=e[i].next){ if(d[e[i].to] == d[u] + 1 && (f=dfs(e[i].to,min(low,e[i].cap - e[i].flow)))){ // tmp += f; e[i].flow += f; e[i^1].flow -= f; // low -= f; // if(!low)break; return f; } } return 0; } void init(){ memset(head,-1,sizeof(head)); tot = 0; } int du[maxn],dn[maxn],ans[maxn]; int main(){ int u,v,down,up; while(~scanf("%d%d",&n,&m)){ init(); for(int i=1;i<=m;i++){ scanf("%d%d%d%d",&u,&v,&down,&up); add(u,v,up-down,0,i); du[u] -= down; du[v] += down; dn[i] = down; } S = 0;T=n+1; int Edge = tot; for(int i=1;i<=n;i++){ if(du[i] > 0) add(S,i,du[i],0,0); if(du[i] < 0) add(i,T,-du[i],0,0); } while(bfs()) { for(int i=0; i<n+2; i++) work[i]=head[i]; while(dfs(S,oo)); } int flag = 0; for(int i=head[S];i!=-1;i=e[i].next){ if(e[i].flow != e[i].cap){ flag = 1;break; } } if(flag)puts("NO"); else { puts("YES"); for(int i = 0;i<Edge;i++) ans[id[i]] = e[i].flow; for(int i=1;i<=m;i++) printf("%d\n",ans[i]+dn[i]); } } }
sgu 194上下界网络流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。