zoj3229:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3442
题意：一个摄影师，在n天内给m个女神拍照。每个女神至少要拍Gi张照片，每一天只能给Ci个女神照相，每一天只能只能拍Di张照片，并且每个女神每天被拍的数量在[l,r]之间。问是否存在一种方案，满足条件，如果满足，最多可以照多少照片。
题解：这是一条有源汇的有上下界的最大流。首先源点s，t，源点和每一天i建立一边，上界为Di，下界为0，每个女神和t建立一边，上界是无穷，下界是Gi，因为上界是无穷大，所以下界等同为0，然后是每一天与对应的女神之间就是流量范围是[l,r],这里就可以转化成有上下界的流量处理，最后t-->s建立一边，容量是INF，这样就转化成无汇源的可行流。接下就是设超级源点ss，超级会点tt,把上面的图按照可行流的求解方式来求解。如果所有ss的出边都是满流，则有可行解。然后再跑一边最大流，此时源点时s，t，这里不再是超级源点ss，和会点tt。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 1000000000
const int N=;
struct Node {
int c;
int f;
}map[N][N];
int sx,ex,n,m;
int pre[N];
int du[N],down[N][N];
bool BFS(int x) { //BFS搜索层次网络
memset(pre,,sizeof(pre));
queue< int > Q;
Q.push(sx);
pre[sx]=;
while(!Q.empty()) {
int d=Q.front();
Q.pop();
for(int i=; i<=x; i++) {
if(!pre[i]&&map[d][i].c-map[d][i].f) {
pre[i]=pre[d]+;
Q.push(i);
}
}
}
return pre[ex]!=;
}
int dinic(int pos,int flow,int x) { //pos是顶点号，flow是当前顶点所能得到的流量,一次dinic只能求出一次增加的流量，
int f=flow;
if(pos==ex)
return flow;
for(int i=; i<=x; i++) {
if(map[pos][i].c-map[pos][i].f&&pre[pos]+==pre[i]) {
int a=map[pos][i].c-map[pos][i].f;
int t=dinic(i,min(a,flow),x);
map[pos][i].f+=t;
map[i][pos].f-=t;
flow-=t;
if(flow<=)break;
//我最开始就是这里没弄明白，我不明白为什么要此顶点得到的流量减去改变量；
//答案就在下面的 return f-flow;
}
}
if(f-flow<=)pre[pos]=-;
return f-flow;//其实这里返回给他前一层的就是这个t;因为t在层函数里面都有，所以所过避免重复就写成这样；
}
int solve(int x){
int sum=;
while(BFS(x)) {
sum+=dinic(sx,INF,x);
}
return sum;
}
int main() {
int u,v,w,t1,t2,t3;
while(~scanf("%d%d",&n,&m)) {
int s=m+n+,t=s+;
sx=t+,ex=sx+;
memset(map,,sizeof(map));
memset(du,,sizeof(du));
memset(down,-,sizeof(down));
for(int i=;i<=m; i++) {
scanf("%d",&w);
du[i]-=w;
du[t]+=w;
map[i][t].c+=INF;
}
for(int i=;i<=n;i++){
scanf("%d%d",&u,&v);
map[s][i+m].c+=v;
while(u--){
scanf("%d%d%d",&t1,&t2,&t3);
du[t1+]+=t2;
du[i+m]-=t2;
down[i+m][t1+]=t2;
map[i+m][t1+].c+=(t3-t2);
}
}
map[t][s].c=INF;
int sum=;
for(int i=;i<=t;i++){
if(du[i]>){
map[sx][i].c+=du[i];
sum+=du[i];
}
else{
map[i][ex].c+=(-du[i]);
}
}
if(solve(n+m+)!=sum)puts("-1");
else{
sx=s,ex=t;
printf("%d\n",solve(n+m+));
for(int i=m+;i<=n+m;i++){
for(int j=;j<=m;j++){
if(down[i][j]>=){
printf("%d\n",map[i][j].f+down[i][j]);
}
}
}
}
puts("");
}
return ;
}