poj 2396 Budget 有上下界的网络流
对上下界网络流的解法很多地方有，就不再叙述了，说说自己的理解，网络流的算法能解决分配的问题，而上下界网络流的不同在于下界必须流满，所以做法就是先用网络流算法把下界流满，然后转化成普通网络流算法解决。
#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn=2e2+9,inf=1e9,N=10000,M=1000;int low[maxn][maxn],up[maxn][maxn];int st[maxn][maxn],ed[maxn][maxn];int r[maxn],c[maxn];int n,m;int S,T,SS,TT;int que[N*2],level[N*2];int head[N*2],lon;bool flag;struct{ int w,c,to,next;}e[100000];void edgeini(){ memset(head,-1,sizeof(head)); lon=-1;}void edgemake(int from,int to,int c){ if(from==0||to==0) cout<<lon<<endl; e[++lon].c=c; e[lon].to=to; e[lon].next=head[from]; head[from]=lon;}void make(int rr,int cc,char tmp,int txt){ int ns,nt,ms,mt; if(rr!=0) ns=nt=rr; else ns=1,nt=n; if(cc!=0) ms=mt=cc; else ms=1,mt=m; for(int i=ns;i<=nt;i++) for(int j=ms;j<=mt;j++) { if(tmp=='>') low[i][j]=max(low[i][j],txt+1); else if(tmp=='<') up[i][j]=min(up[i][j],txt-1); else { low[i][j]=max(low[i][j],txt); up[i][j]=min(up[i][j],txt); } }}void makegraph(){ edgemake(TT,SS,inf); edgemake(SS,TT,0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(up[i][j]>=low[i][j]) { edgemake(st[i][j],ed[i][j],up[i][j]-low[i][j]); edgemake(ed[i][j],st[i][j],0); } else flag=false; if(low[i][j]) { edgemake(S,ed[i][j],low[i][j]); edgemake(ed[i][j],S,0); edgemake(st[i][j],T,low[i][j]); edgemake(T,st[i][j],0); } } for(int i=1;i<=n;i++) { edgemake(SS,i+N,r[i]); edgemake(i+N,SS,0); for(int j=1;j<=m;j++) { edgemake(i+N,st[i][j],inf); edgemake(st[i][j],i+N,0); } } for(int i=1;i<=m;i++) { edgemake(i+N+M,TT,c[i]); edgemake(TT,i+N+M,0); for(int j=1;j<=n;j++) { edgemake(ed[j][i],i+N+M,inf); edgemake(i+N+M,ed[j][i],0); } }}bool makelevel(int s,int t){ memset(level,0,sizeof(level)); int front=1,end=0; que[++end]=s; level[s]=1; while(front<=end) { int u=que[front++];// cout<<u<<endl; if(u==t) return true; for(int k=head[u];k!=-1;k=e[k].next) { int v=e[k].to; if(!level[v]&&e[k].c) { level[v]=level[u]+1; que[++end]=v; } } } return false;}int dfs(int now,int t,int maxf){ if(now==t) return maxf; int ret=0; for(int k=head[now];k!=-1;k=e[k].next) { int u=e[k].to; if(e[k].c==0||level[u]!=level[now]+1) continue; int f=dfs(u,t,min(e[k].c,maxf-ret));// if(e[k].c<f) cout<<k<<endl; e[k].c-=f; e[k^1].c+=f; ret+=f; if(ret==maxf) return ret; } return ret;}int maxflow(int s,int t){ int ret=0; while(makelevel(s,t)) { ret+=dfs(s,t,inf); } return ret;}void prin(){ for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { int k=head[st[i][j]]; while(e[k].to!=ed[i][j]) k=e[k].next; printf("%d ",low[i][j]+e[k^1].c); } cout<<endl; }}int main(){// freopen("in.txt","r",stdin); int TTT; scanf("%d",&TTT); while(TTT--) { flag=true; edgeini(); memset(up,50,sizeof(up)); memset(low,0,sizeof(low)); scanf("%d%d",&n,&m); SS=1,TT=2,S=3,T=4; for(int i=1,tt=2;i<=n;i++) for(int j=1;j<=m;j++) { tt++; st[i][j]=tt*2-1; ed[i][j]=tt*2; } for(int i=1;i<=n;i++) scanf("%d",&r[i]); for(int i=1;i<=m;i++) scanf("%d",&c[i]); { int p,rr,cc,txt; char tmp[10]; scanf("%d",&p); while(p--) { scanf("%d%d%s%d",&rr,&cc,tmp+1,&txt); make(rr,cc,tmp[1],txt); } } makegraph();// for(int i=1;i<=n;i++)// {// for(int j=1;j<=m;j++)// printf("%d ",low[i][j]);// cout<<endl;// }// for(int i=1;i<=n;i++)// {// for(int j=1;j<=m;j++)// printf("%d ",up[i][j]);// cout<<endl;// }// for(int k=head[5];k!=-1;k=e[k].next)// cout<<e[k].to<<endl;// for(int k=head[S];k!=-1;k=e[k].next)// cout<<e[k].c<<endl; if(!flag) { printf("IMPOSSIBLE\n"); continue; } int now=maxflow(S,T); int sum=0; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum+=low[i][j]; if(sum!=now) { printf("IMPOSSIBLE\n"); continue; } e[0].c=0; e[1].c=0; for(int k=head[S];k!=-1;k=e[k].next) e[k].c=0; for(int k=head[T];k!=-1;k=e[k].next) e[k].c=0; now+=maxflow(SS,TT); int sum1=0,sum2=0; for(int i=1;i<=n;i++) sum1+=r[i]; for(int i=1;i<=m;i++) sum2+=c[i]; if(sum1==sum2&&sum1==now) { prin(); } else { printf("IMPOSSIBLE\n"); } if(TTT) cout<<endl; } return 0;}