zoj 2314
#include <bits/stdc++.h> using namespace std; const int maxn=100000; #define INF 1e9 int s,t,tt,l,n,m; int head[maxn],d[maxn],low[maxn],in[maxn]; bool vis[maxn]; struct re{ int a,b,c,from,flow; }a[maxn]; void arr(int x,int y,int z) { a[++l].a=head[x]; a[l].from=x; a[l].b=y; a[l].c=z; a[l].flow=0; head[x]=l; } bool bfs(){ memset(vis,0,sizeof(vis)); queue<int> q; q.push(s); d[s]=0; vis[s]=1; while (!q.empty()) { int x=q.front(); q.pop(); int u=head[x]; while (u) { int v=a[u].b; if (!vis[v]&&a[u].c>a[u].flow) { vis[v]=1; d[v]=d[x]+1; q.push(v); } u=a[u].a; } } return(vis[t]); } int dfs(int x,int y) { if (x==t||y==0) { return y; } int flow=0,f,tmp; int u=head[x]; while (u) { int v=a[u].b; if (d[x]+1==d[v]&&(f=dfs(v,min(y,a[u].c-a[u].flow)))>0) { a[u].flow+=f; if (u%2) tmp=u+1; else tmp=u-1; a[tmp].flow-=f; flow+=f; y-=f; } u=a[u].a; } return(flow); } int maxflow() { int flow=0; while (bfs()) { flow+=dfs(s,INF); } return flow; } int main() { freopen("noip.in","r",stdin); freopen("noip.out","w",stdout); ios::sync_with_stdio(false); cin>>tt; while (tt--) { l=0; memset(head,0,sizeof(head)); cin>>n>>m; memset(in,0,sizeof(in)); int c,d,e,f; for (int i=1;i<=m;i++) { cin>>c>>d>>e>>f; low[i]=e; in[c]-=e; in[d]+=e; arr(c,d,f-e); arr(d,c,0); } int sum=0; for (int i=1;i<=n;i++) { if (in[i]>0) sum+=in[i]; if (in[i]>0) { arr(0,i,in[i]); arr(i,0,0); } if (in[i]<0) { arr(i,n+1,-in[i]); arr(n+1,i,0); } } s=0; t=n+1; int tmpw=maxflow(); if (sum==tmpw) { cout<<"YES"<<endl; for (int i=1;i<=m;i++) cout<<low[i]+a[i*2-1].flow<<endl; } else { cout<<"NO"<<endl; } cout<<endl; } return 0; }
2.求有源有汇有下界最大流
建图与上面一样，把原来的汇点向源点连边INF
之后先求一遍可行流
之后再割掉t-s的边去求最大流
最终的答案即dinic+e[t--->s].flow(就是求可行流的时候的流量）
然后来建图：引入源点S汇点T，n天一天一点，m个少女每人一点。S到每一天连一条边，上界为Dt，下界为0。每个少女到汇点连一条边，上界为无穷大，下界为Gi。对每一天，连一条边到所有要拍照的少女，下界为L，上界为R。然后引入超级源点SS，超级汇点TT，像无源无汇上下界可行流那样建边，然后T到S连一条边，容量为无穷大。最后从源点S到汇点T跑一遍最大流就是答案，每条边容量的取法和无源无汇上下界可行流一样。
小证明：原图为什么是那样建的我就不解释了。
至于加入超级源点和超级汇点之后为什么要连一条边T→S呢，因为根据无源无汇上下界可行流的做法，原图无源无汇，是应该有一个环的，而现在没有……
之后再从S到T跑一遍，会不会影响之前的流量下界呢？满足下界是来自于点与超级源点和超级汇点之间的边，如果我们把这两个点删掉，边的容量就没法变了，也就不会影响到流量下界。而我没有删掉，是因为若求出可行解之后，超级源点和超级汇点关联的边都应该是满流量的，再跑最大流不可能经过这两个点。
那么跑可行流的时候，和跑最大流的时候，流量是分开算的，那为什么不用加上原来可行流的流量呢？因为原先我们连了一条边T→S，根据无源无汇图中，每个点的入流等于出流，跑可行流的流量已经存在了T→S这条边中，跑最大流就时候，T→S的反向边就有了可行流的容量。所以跑最大流的时候会加上可行流的容量，就不用再加一遍了。
3.求有源汇最小流算法
3、做一次maxflow（）。
4、源点（Sd）和起点（St）连一条容量为oo的边。
5、再做一次maxflow（）。
6、当且仅当所有附加弧满载时有可行流，最后答案为flow[（Sd->St）^1]，St到Sd最大流就是Sd到St最小流。