题目大意： 一个XX用n天要给m个女神拍写真。这n天里每个女神i分别至少要拍Gi张照片，XX在第j天会给指定Cj个女神最多拍Dj张照片，每个女神第j天拍照数在lj到hj张照片。问XX是否安排完成他的任务，不能输出-1，如果能的话，让他尽可能多拍照。先输出他最多能拍的张数，然后对于输入每一行提到要拍照的女神，按照顺序输出当天那个女神要拍照的张数。（就描述到这了，更多请访问下面的链接）
题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3442。
这是一道很典型的有源汇的上下界最大流。
容我鸣谢一下先：http://www.cnblogs.com/kane0526/archive/2013/04/05/3001108.html，我是看了这里报告，自己再搜索资料整理的。
再鸣谢：http://fayaa.com/code/view/26516/是这个帮助我真正理解了的代码（也不是这么说，主要是因为***），虽然这里没有任何语言描述，但博主的代码是SAP实现，容小菜我偷个懒，网络流我都倾向SAP，不习惯dinic，而其他博客一般都是dinic算法写的，读起来太累了。
好吧，还是返回主题了。通常我们求的最大流是上界最大流，而下界都是0。对于无源汇的上下界最大流，大家应该不难理解，把下界边差量du[i]（一会儿解释）直接跟我们定义的源点和汇点连起来，*边（上界边-下界边）按原图留下。现在想想，下界边一定对应一点是入、另一个点是出，若du[i] = in[i]-out[i]，那么当du[i]为正时，表明对于点i，一定要流进du[i]，我们连边source --> i with capacity = du[i]，否则对于点i一定要流出-du[i]，我们连边 i --> sink with capacity = -du[i]。这些就是上下界的全部逻辑翻译了。如果把 sum = sigma(du[i] | du[i] > 0) （或者sum = -sigma(du[i] | du[i] < 0)），那么对构造这个图求一遍最大流，如果maxflow = sum，证明所有限制都能满足了。
当然，有的题目还有一些要求，比如这道题里的：拍照数尽可能多，这就需要后续工作了。当然对于这道题，还有一个特殊的地方，它是有自定义源汇的。那如何把变成无源汇的呢？很简单，假设ss、tt分别是题目定义的源点和汇点，连一条边 tt --> ss with capacity = infinity。这样就形成了环回的一个无源汇的网络图。另外自己再定义超级源点汇点，按照上一段描述得构图判所有限制是否能满足所有限制。
（*）若满足，重设源点、汇点为题目自定义源点、汇点，对于残余网络图求一遍最大流。最后，把网络图里的流入出情况从记录的边中读出来还原出答案就好了。
特别说明一下，有很多博客里都一再强调：对于上一段求最大流时要删掉自定义超级源点、汇点和 ”tt --> ss with capacity = infinity“这条环回边。我是怎么也理解不了了。超级源点只出不入，超级汇点只入不出，它们干那些博主们毛线事？？？为什么要删掉？？？环回边的逆向边记录有要满足所有限制必须的流量值。。。删了，你还去哪找更稳妥的这个值？？？？也许我不了解dinic算法，没理解出这些话的强大含义。。。弱弱可以YY一下不，会不会是原始博主写这句话时是他还在学花拳绣腿的时候，而他现在忘了改过来，而千万学习者就未加思索的加上来了呢？反正我是，仅仅更改源点、汇点后，直接对残余网络求最大流AC的。
贴上代码：欢迎大神们提出珍贵建议。
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = ;
const int maxe = ;
const int maxf = (-)^(<<);
#define smaller(a,b) ((a)<(b)?(a):(b))
struct edge{
int u,v,c;
edge(int a=,int b=,int d=){ u=a, v=b, c=d; }
}e[maxe];
int head[maxn];
int next[maxe];
int cnt;
void add(int u,int v,int c){
e[cnt] = edge(u,v,c);
next[cnt] = head[u], head[u] = cnt++;
//printf("cnt = %d,\t%d --> %d with c = %d, next = %d\n",cnt-1,u,v,c,next[cnt-1]);
e[cnt] = edge(v,u,);
next[cnt] = head[v], head[v] = cnt++;
}
//***********************************//
int source,sink,maxdep;
int dep[maxn],gap[maxn];
int cur[maxn],trace[maxn],que[maxn],top;
void setGD(){
for(int i=;i<=maxdep;i++) dep[i] = maxdep;
dep[sink] = ;
int front,rear,u,v;
front = rear = ;
que[rear++] = sink;
while(front != rear){
u = que[front++];
if(front >= maxn) front = ;
for(int i=head[u];i!=-;i=next[i]){
v = e[i].v;
//if(v > maxdep) continue; //这句是删掉超级源点、汇点的句子，删不删都AC。。。
if(dep[v] < maxdep) continue; //if(e[i].c || dep[v] <= dep[u]+1) continue; //不是逆向边，或者'被访问过'
dep[v] = dep[u]+;
que[rear++] = v;
if(rear >= maxn) rear = ;
}
}
memset(gap,,sizeof(gap));
for(int i=;i<=maxdep;i++) gap[dep[i]]++;
}
int maxF(){
setGD();
for(int i=;i<=maxdep;i++) cur[i] = head[i];
int u=source,flow=,i;
top = ;
while(dep[source] <= maxdep){
if(u == sink){
int tf = maxf,ins;
for(i=;i<top;i++){ //找瓶颈边
if(tf > e[trace[i]].c){
tf = e[trace[i]].c;
ins = i;
}
}
/*
for(i=0;i<top;i++)
printf("%d -> ",e[trace[i]].u);
printf("%d , temp_flow = %d\n",e[trace[top-1]].v,tf);
*/
for(i=;i<top;i++){
e[trace[i]].c -= tf;
e[trace[i]^].c += tf;
}
flow += tf;
u = e[trace[ins]].u, top = ins;
}
if(u != sink && gap[dep[u]-]==) break;
for(i=cur[u];i!=-;i=next[i])
if(e[i].c > && dep[u] == dep[e[i].v] + )
break;
if(i != -) {
trace[top++] = i;
cur[u] = i;
u = e[i].v;
}
else {
int mindep = maxdep;
for(i=head[u];i!=-;i=next[i]){
if(e[i].c && dep[e[i].v] < mindep)
mindep = dep[e[i].v], cur[u] = i;
}
gap[dep[u]]--;
dep[u] = mindep + ;
gap[dep[u]]++;
if(u != source)
u = e[trace[--top]].u;
}
}
return flow;
}
//**********************************//
int in[maxn],out[maxn],du[maxn],basement;
int lownm[][];
int order[][],oidx[];
void initial()
{
cnt = ;
memset(head,-,sizeof(head));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
memset(lownm,,sizeof(lownm));
//initial source ,sink and maxdep;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m) != EOF){
initial();
source = n+m+;
sink = source+;
maxdep = sink+;
int ss=n+m+;
int tt=ss+;
int fsum = ;
basement = tt;
for(int i=;i<m;i++)
scanf("%d",&out[i+n]), in[tt]+=out[i+n], add(i+n,tt,maxf-out[i+n]);
int c,d;
for(int nn=;nn<n;nn++){
scanf("%d%d",&c,&d);
oidx[nn] = c;
add(ss,nn,d);
int girl,low,up;
for(int cc=;cc<c;cc++){
scanf("%d%d%d",&girl,&low,&up);
lownm[nn][girl]=low;
add(nn,n+girl,up-low);
out[nn]+=low;
in[n+girl] += low;
order[nn][cc] = girl;
}
}
int fcnt = cnt;
add(tt,ss,maxf);
int sum = ;
for(int i=;i<=basement;i++){
du[i] = in[i]-out[i];
if(du[i] > ) add(source,i,du[i]), sum+=du[i];
else if(du[i] < ) add(i,sink,-du[i]);
}
int flow = maxF();
if(flow < sum) printf("-1\n\n");
else {
source = ss;
sink = tt;
maxdep = sink+;
//e[fcnt].c = 0, e[fcnt^1] = 0;
flow = maxF();
for(int i=;i<n;i++)
for(int j=head[i];j>=;j=next[j])
if(!(j&))
lownm[i][e[j].v-n] += e[j^].c;
//flow = 0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) flow += lownm[i][j];
printf("%d\n",flow);
for(int i=;i<n;i++)
for(int j=;j<oidx[i];j++)
printf("%d\n",lownm[i][order[i][j]]);
puts("");
}
}
return ;
}
另外在贴上一个未AC的代码，这个代码错在构图，***调了我8个小时，还是没搞定。。。
我当时的构图思路是这样的： source --> 某个女神 --> 某一天 --> 汇点。结果就弹了一天。
后来AC代码改成：source --> 某一天 --> 某个女神--> 汇点。很怀疑是这个special judge的判题程序弱爆了。请有能力的大神给我指点迷津啊。。。
代码如下，请大神斧正！
/*
构图。。。不解，未AC
*/
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn = ;
const int maxe = ;
const int maxf = (-)^(<<);
#define smaller(a,b) ((a)<(b)?(a):(b))
struct edge{
int u,v,c;
edge(int a=,int b=,int d=){ u=a, v=b, c=d; }
}e[maxe];
int head[maxn];
int next[maxe];
int cnt;
void add(int u,int v,int c){
e[cnt] = edge(u,v,c);
next[cnt] = head[u], head[u] = cnt++;
//printf("cnt = %d,\t%d --> %d with c = %d, next = %d\n",cnt-1,u,v,c,next[cnt-1]);
e[cnt] = edge(v,u,);
next[cnt] = head[v], head[v] = cnt++;
}
//***********************************//
int source,sink,maxdep;
int dep[maxn],gap[maxn];
int cur[maxn],trace[maxn],que[maxn],top;
void setGD(){
for(int i=;i<=maxdep;i++) dep[i] = maxdep;
dep[sink] = ;
int front,rear,u,v;
front = rear = ;
que[rear++] = sink;
while(front != rear){
u = que[front++];
if(front >= maxn) front = ;
for(int i=head[u];i!=-;i=next[i]){
v = e[i].v;
if(v > maxdep) continue;
if(dep[v] < maxdep) continue; //if(e[i].c || dep[v] <= dep[u]+1) continue; //不是逆向边，或者'被访问过'
dep[v] = dep[u]+;
que[rear++] = v;
if(rear >= maxn) rear = ;
}
}
memset(gap,,sizeof(gap));
for(int i=;i<=maxdep;i++) gap[dep[i]]++;
}
int maxF(){
setGD();
for(int i=;i<=maxdep;i++) cur[i] = head[i];
int u=source,flow=,i;
top = ;
while(dep[source] <= maxdep){
if(u == sink){
int tf = maxf,ins;
for(i=;i<top;i++){ //找瓶颈边
if(tf > e[trace[i]].c){
tf = e[trace[i]].c;
ins = i;
}
}
/*
for(i=0;i<top;i++)
printf("%d -> ",e[trace[i]].u);
printf("%d , temp_flow = %d\n",e[trace[top-1]].v,tf);
*/
for(i=;i<top;i++){
e[trace[i]].c -= tf;
e[trace[i]^].c += tf;
}
flow += tf;
u = e[trace[ins]].u, top = ins;
}
if(u != sink && gap[dep[u]-]==) break;
for(i=cur[u];i!=-;i=next[i])
if(e[i].c > && dep[u] == dep[e[i].v] + )
break;
if(i != -) {
trace[top++] = i;
cur[u] = i;
u = e[i].v;
}
else {
int mindep = maxdep;
for(i=head[u];i!=-;i=next[i]){
if(e[i].c && dep[e[i].v] < mindep)
mindep = dep[e[i].v], cur[u] = i;
}
gap[dep[u]]--;
dep[u] = mindep + ;
gap[dep[u]]++;
if(u != source)
u = e[trace[--top]].u;
}
}
return flow;
}
//**********************************//
int in[maxn],out[maxn],du[maxn],basement;
int lownm[][];
int order[][],oidx[];
void initial()
{
cnt = ;
memset(head,-,sizeof(head));
memset(in,,sizeof(in));
memset(out,,sizeof(out));
memset(lownm,,sizeof(lownm));
//initial source ,sink and maxdep;
}
int main()
{
int n,m;
while(scanf("%d%d",&n,&m) != EOF){
initial();
source = n+m+;
sink = source+;
maxdep = sink+;
int ss=n+m+;
int tt=ss+;
int fsum = ;
basement = tt;
for(int i=;i<m;i++)
scanf("%d",&in[i]), out[ss]+=in[i], add(ss,i,maxf), fsum+=in[i];
int c,d;
for(int nn=;nn<n;nn++){
scanf("%d%d",&c,&d);
oidx[nn] = c;
int girl,low,up;
for(int cc=;cc<c;cc++){
scanf("%d%d%d",&girl,&low,&up);
lownm[nn][girl]=low;
add(girl,m+nn,up-low);
out[girl]+=low;
in[m+nn] +=low;
order[nn][cc] = girl;
}
add(m+nn,tt,d);
}
int fcnt = cnt;
add(tt,ss,maxf);
int sum = ;
for(int i=;i<=basement;i++){
du[i] = in[i]-out[i];
if(du[i] > ) add(source,i,du[i]), sum+=du[i];
else if(du[i] < ) add(i,sink,-du[i]);
}
int flow = maxF();
int flag = ;
for(int i=head[source];i>=;i=next[i])
if(e[i].c){
flag = ;
break;
}
if(!flag) printf("-1\n\n");
else {
source = ss;
sink = tt;
maxdep = sink+;
//e[fcnt].c = 0, e[fcnt^1] = 0;
flow = maxF();
for(int i=n+m;i>=m;i--)
for(int j=head[i];j>=;j=next[j])
if(j&)
lownm[i-m][e[j].v] += e[j].c;
//flow = 0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) flow += lownm[i][j];
printf("%d\n",flow);
for(int i=;i<n;i++)
for(int j=;j<oidx[i];j++)
printf("%d\n",lownm[i][order[i][j]]);
puts("");
}
}
return ;
}