链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1314
题意：某恐怖组织要建立一个核反应堆，他们需要设计一个冷却系统，n个点由m个管子连接，为使液体循环流动，每个节点的总流入量需要等于总流出量，现告诉你每根管子的最小流量及最@R_431_403@及它们连接的两点（有向），问是否存在可行流，如存在，输出每个管子的流量。
有上下界的网络流分为四种：无源汇的上下界可行流、有源汇的上下界可行流、有源汇的上下界最大流、有源汇的上下界最小流，这道是其中第一种。
这道题是裸题，直接说这类题的建图方式。
建图：这类题建图一般是建原图的伴随网络，根据伴随网络求是否存在可行流，继而求出每条弧的流量。伴随网络这样建立，新增超级源点Vs和超级汇点Vt，然后对每个顶点u求D（u）值，即流入顶点u的所有边的下界和 减去 流出顶点u的所有边的下界和，然后对于每个顶点u，如果D（u）> 0，新增一条从Vs流向u容量为D（u）的弧，如果D（u）< 0，新增一条从u流向Vt容量为-D（u）的弧，D（u）=0则不添加，D（u）反过来减也可以，网上也有那种减的写法，但是连边时也得反过来，即D（u）> 0时连向Vt，D（u）< 0时从Vs连过来。对于原图中的弧，伴随网络中也要建立，只不过弧的容量变为上界减下界，即一条无最小流限制的弧。
证明方法我不贴了，网上有很多，想法很厉害。
isap代码
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 500100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define mod 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct Edge{ int u,v,w,next; }edge[500000]; int head[220],dist[220],cur[220],fa[220],num[220]; int n,src,sink,cnt,nn; void add_edge(int a,int b,int c){ edge[cnt].u = a; edge[cnt].v = b; edge[cnt].w = c; edge[cnt].next = head[a]; head[a] = cnt++; } void bfs() { int x,i,j; queue<int> q; memset(dist,-1,sizeof(dist)); q.push(sink); dist[sink] = 0; while(!q.empty()){ x = q.front(); q.pop(); for(i=head[x];i!=-1;i=edge[i].next){ if(dist[edge[i].v]<0){ dist[edge[i].v] = dist[x] + 1; q.push(edge[i].v); } } } } int augment() { int x=sink,a=INF; while(x!=src){ a = min(a,edge[fa[x]].w); x = edge[fa[x]].u; } x=sink; while(x!=src){ edge[fa[x]].w -= a; edge[fa[x]^1].w += a; x = edge[fa[x]].u; } return a; } int isap() { int i,x,ok,minm,flow=0; memset(num,sizeof(num)); bfs(); for(i=0;i<=n+1;i++) num[dist[i]]++; for(i=0;i<=n+1;i++) cur[i] = head[i]; x=src; while(dist[src]<nn){ if(x==sink){ flow += augment(); x = src; } ok=0; for(i=cur[x];i!=-1;i=edge[i].next){ if(edge[i].w && dist[x]==dist[edge[i].v]+1){ ok=1; fa[edge[i].v] = i; cur[x] = i; x = edge[i].v; break; } } if(!ok){ minm = nn; for(i=head[x];i!=-1;i=edge[i].next) if(edge[i].w && dist[edge[i].v]<minm) minm=dist[edge[i].v]; if(--num[dist[x]]==0)break; num[dist[x]=minm+1]++; cur[x]=head[x]; if(x!=src) x=edge[fa[x]].u; } } return flow; } int D[50000]; int low[50000]; int main(){ int i,j,t; int a,b,c,d; scanf("%d",&t); while(t--){ memset(head,sizeof(head)); memset(D,sizeof(D)); scanf("%d%d",&n,&m); cnt = 0; src = 0; sink = n + 1; nn = sink + 1; for(i=0;i<m;i++){ scanf("%d%d%d%d",&a,&b,&low[i],&d); D[b] += low[i]; D[a] -= low[i]; add_edge(a,d-low[i]); add_edge(b,a,0); } for(i=1;i<=n;i++){ if(D[i]==0) continue; if(D[i]>0){ add_edge(src,D[i]); add_edge(i,0); } else{ add_edge(i,-D[i]); add_edge(sink,0); } } int ans = 0; ans = isap(); //cout<<ans<<endl; int flag = 0; for(i=head[src];i!=-1;i=edge[i].next){ if(edge[i].w!=0){ flag = 1; break; } } if(!flag){ for(i=head[sink];i!=-1;i=edge[i].next){ if(edge[i^1].w!=0){ flag = 1; break; } } } if(flag) puts("NO"); else{ puts("YES"); for(i=0;i<m;i++){ printf("%d\n",edge[(i*2)^1].w+low[i]); } } puts(""); } return 0; }
Dinic代码
#include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 500100 #define eps 1e-7 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define mod 1000000007 #define ll long long #define ull unsigned ll #define lson l,rt<<1|1 struct node{ int u,next; int ww; }edge[MAXN]; int head[220],dist[220]; int n,sink; int low[50100],D[50100]; void add_edge(int a,int c){ edge[cnt].u = b; edge[cnt].w = c; edge[cnt].next = head[a]; head[a] = cnt++; } bool bfs(){ int i,j; memset(dist,sizeof(dist)); dist[src] = 1; queue<int>q; q.push(src); while(!q.empty()){ int u = q.front(); q.pop(); for(i=head[u];i!=-1;i=edge[i].next){ int v = edge[i].u; if(dist[v]==-1&&edge[i].w){ dist[v] = dist[u] + 1; q.push(v); } } } if(dist[sink]!=-1) return true; return false; } int dfs(int u,int delta){ int i,dd; if(u==sink||delta==0) return delta; int ret = 0; for(i=head[u];i!=-1;i=edge[i].next){ int v = edge[i].u; if(dist[v]==dist[u]+1&&edge[i].w){ dd = dfs(v,min(delta,edge[i].w)); edge[i].w -= dd; edge[i^1].w += dd; delta -= dd; ret += dd; } } return ret; } int main(){ int i,&m); cnt = 0; src = 0; sink = n + 1; for(i=0;i<m;i++){ scanf("%d%d%d%d",0); } } int ans = 0; while(bfs()){ ans += dfs(src,INF); } //cout<<ans<<endl; int flag = 0; for(i=head[src];i!=-1;i=edge[i].next){ if(edge[i].w!=0){ flag = 1; break; } } if(!flag){ for(i=head[sink];i!=-1;i=edge[i].next){ if(edge[i^1].w!=0){ flag = 1; break; } } } if(flag) puts("NO"); else{ puts("YES"); for(i=0;i<m;i++){ printf("%d\n",edge[(i*2)^1].w+low[i]); } } puts(""); } return 0; }
