无源汇上下界可行流
n 个点，m 条边，每条边 有一个流量下界 和流量上界 ，求一种可行方案使得在所有点满足流量平衡条件的前提下，所有边满足流量限制。
建立超级源点和汇点 每条边连 上界-下界 统计总的流入和流出 如果大于0(流入多）连 s-i-d[i] 否则 i-t- -d[i]
然后跑 dinic即可 如果满流即有解 答案要加上下界
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=4e5+44; const int M=4e6+54; int d[N]; struct edge { int to, next, w; } e[M << 1]; int head[N], cnt = 1; void add(int x, int y, int z) { e[++cnt] = (edge){y, head[x], z}; head[x] = cnt; e[++cnt] = (edge){x, head[y], 0}; head[y] = cnt; } void ins(int x,int y,int a,int b) { add(x,y,b-a); d[x]-=a; d[y]+=a; } int level[N]; bool bfs(int s, int t) { memset(level, 0, sizeof level); queue<int> q; level[s] = 1; q.push(s); while (!q.empty()) { int pos = q.front(); q.pop(); for (int i = head[pos]; i; i = e[i].next) { int nx = e[i].to; if (!e[i].w || level[nx]) continue; level[nx] = level[pos] + 1; q.push(nx); } } return level[t]; } int dfs(int s, int t, int flow) { if (s == t) return flow; int ret = 0; for (int i = head[s]; flow && i; i = e[i].next) { int nx = e[i].to; if (level[nx] == level[s] + 1 && e[i].w) { int tmp = dfs(nx, t, min(flow, e[i].w)); e[i].w -= tmp; e[i ^ 1].w += tmp; flow -= tmp; ret += tmp; } } if (!ret) level[s] = 0; return ret; } int dinic(int s, int t) { int ret = 0; while (bfs(s, t)) ret += dfs(s, t, inf); return ret; } int n,m,s,t,a,b,c,sum; int ans[N]; int main() { cin>>n>>m; s=n+1,t=s+1; rep(i,1,m) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); ins(a,b,c,d); ans[i]=c; } rep(i,1,n) if(d[i]>0)add(s,i,d[i]),sum+=d[i]; else if(d[i]<0) add(i,t,-d[i]); if(dinic(s,t)!=sum) { printf("NO "); } else { cout<<"YES"<<endl; for(int i=1,j=3;i<=m;i++,j+=2) printf("%d ",ans[i]+e[j].w); } return 0; }
有源汇上下界可行流
从 T 到 S 连一条下界为 0 ，上界为 +inf 的边，把汇流入的流量转移给源流出的流量，转化为无源汇的网络，然后求解无源汇上下界可行流。
有源汇上下界最大流
和有源汇上下界可行流非常像 最后再跑一次原来的s t 的dinic就是答案
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=4e5+44; const int M=4e6+54; int d[N]; struct edge { int to, next, w; } e[M << 1]; int head[N], cnt = 1; void add(int x, int y, int z) { e[++cnt] = (edge){y, head[x], z}; head[x] = cnt; e[++cnt] = (edge){x, head[y], 0}; head[y] = cnt; } void ins(int x,int y,int a,int b) { add(x,y,b-a); d[x]-=a; d[y]+=a; } int level[N]; bool bfs(int s, int t) { memset(level, 0, sizeof level); queue<int> q; level[s] = 1; q.push(s); while (!q.empty()) { int pos = q.front(); q.pop(); for (int i = head[pos]; i; i = e[i].next) { int nx = e[i].to; if (!e[i].w || level[nx]) continue; level[nx] = level[pos] + 1; q.push(nx); } } return level[t]; } int dfs(int s, int t, int flow) { if (s == t) return flow; int ret = 0; for (int i = head[s]; flow && i; i = e[i].next) { int nx = e[i].to; if (level[nx] == level[s] + 1 && e[i].w) { int tmp = dfs(nx, t, min(flow, e[i].w)); e[i].w -= tmp; e[i ^ 1].w += tmp; flow -= tmp; ret += tmp; } } if (!ret) level[s] = 0; return ret; } int dinic(int s, int t) { int ret = 0; while (bfs(s, t)) ret += dfs(s, t, inf); return ret; } int n,m,s,t,a,b,c,sum,S,T; int ans[N]; int main() { cin>>n>>m>>s>>t; S=2*n+1,T=S+1; rep(i,1,m) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); ins(a,b,c,d); } ins(t,s,0,inf); rep(i,1,n) if(d[i]>0)add(S,i,d[i]),sum+=d[i]; else if(d[i]<0) add(i,T,-d[i]); if(dinic(S,T)!=sum) { printf("please go home to sleep "); } else { cout<<dinic(s,t); } return 0; }
有源汇上下界最小流
类似有源汇上下界可行流的构图方法，但先不添加 s 到 的边，求一次超级源到超级汇的最大流。然后再添加一条从 T 到 S 下界为 0 ，上界为 +inf 的边，在残量网络上再求一次超级源到超级汇的最大流。流经 t 到 s 的边的流量就是最小流的值。
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define ll long long #define pb push_back #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) ////////////////////////////////// #define inf 0x3f3f3f3f const int N=4e5+44; const int M=4e6+54; int d[N]; struct edge { int to, next, w; } e[M << 1]; int head[N],cur[N],cnt = 1; void add(int x, int y, int z) { e[++cnt] = (edge){y, head[x], z}; head[x] = cnt; e[++cnt] = (edge){x, head[y], 0}; head[y] = cnt; } void ins(int x,int y,int a,int b) { add(x,y,b-a); d[x]-=a; d[y]+=a; } int level[N]; bool bfs(int s, int t) { memset(level, 0, sizeof level); queue<int> q; level[s] = 1; q.push(s); while (!q.empty()) { int pos = q.front();q.pop(); for (int i = head[pos]; i; i = e[i].next) { int nx = e[i].to; if (!e[i].w || level[nx]) continue; level[nx] = level[pos] + 1; q.push(nx); } } return level[t]; } int dfs(int s, int t, int flow) { if(s==t||flow==0)return flow; int f,ret = 0; for (int &i = cur[s],v; i; i = e[i].next) { v = e[i].to; if (level[v] == level[s] + 1 && (f=dfs(v,t,min(flow,e[i].w)))>0) { e[i].w -= f; e[i ^ 1].w += f; flow -= f; ret += f; if(!flow)break; } } return ret; } int dinic(int s, int t) { int ret = 0; while (bfs(s, t)) memcpy(cur,head,sizeof cur),ret += dfs(s, t, inf); return ret; } int n,m,s,t,a,b,c,sum,S,T; int ans[N]; int main() { cin>>n>>m>>s>>t; S=2*n+1,T=S+1; rep(i,1,m) { int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); ins(a,b,c,d); } rep(i,1,n) if(d[i]>0)add(S,i,d[i]),sum+=d[i]; else if(d[i]<0) add(i,T,-d[i]); ll ans=dinic(S,T); add(t,s,inf); ans+=dinic(S,T); if(ans!=sum) printf("please go home to sleep "); else printf("%d ",e[cnt].w); return 0; }