题目大意： 一个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的。
贴上代码：欢迎大神们提出珍贵建议。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5 const int maxn = 1500; 6 const int maxe = 1001001; 7 const int maxf = (-1)^(1<<31); 8 #define smaller(a,b) ((a)<(b)?(a):(b)) 9 struct edge{ 10 int u,v,c; 11 edge(int a=0,int b=0,int d=0){ u=a, v=b, c=d; } 12 }e[maxe]; 13 int head[maxn]; 14 int next[maxe]; 15 int cnt; 16 void add(int u,int v,int c){ 17 e[cnt] = edge(u,v,c); 18 next[cnt] = head[u], head[u] = cnt++; 19 //printf("cnt = %d, %d --> %d with c = %d, next = %d ",cnt-1,u,v,c,next[cnt-1]); 20 e[cnt] = edge(v,u,0); 21 next[cnt] = head[v], head[v] = cnt++; 22 } 23 //***********************************// 24 int source,sink,maxdep; 25 int dep[maxn],gap[maxn]; 26 int cur[maxn],trace[maxn],que[maxn],top; 27 void setGD(){ 28 for(int i=0;i<=maxdep;i++) dep[i] = maxdep; 29 dep[sink] = 0; 30 int front,rear,u,v; 31 front = rear = 0; 32 que[rear++] = sink; 33 while(front != rear){ 34 u = que[front++]; 35 if(front >= maxn) front = 0; 36 for(int i=head[u];i!=-1;i=next[i]){ 37 v = e[i].v; 38 //if(v > maxdep) continue; //这句是删掉超级源点、汇点的句子，删不删都AC。。。 39 if(dep[v] < maxdep) continue; //if(e[i].c || dep[v] <= dep[u]+1) continue; //不是逆向边，或者'被访问过' 40 dep[v] = dep[u]+1; 41 que[rear++] = v; 42 if(rear >= maxn) rear = 0; 43 } 44 } 45 memset(gap,0,sizeof(gap)); 46 for(int i=0;i<=maxdep;i++) gap[dep[i]]++; 47 } 48 int maxF(){ 49 setGD(); 50 for(int i=0;i<=maxdep;i++) cur[i] = head[i]; 51 int u=source,flow=0,i; 52 top = 0; 53 while(dep[source] <= maxdep){ 54 if(u == sink){ 55 int tf = maxf,ins; 56 for(i=0;i<top;i++){ //找瓶颈边 57 if(tf > e[trace[i]].c){ 58 tf = e[trace[i]].c; 59 ins = i; 60 } 61 } 62 /* 63 for(i=0;i<top;i++) 64 printf("%d -> ",e[trace[i]].u); 65 printf("%d , temp_flow = %d ",e[trace[top-1]].v,tf); 66 */ 67 for(i=0;i<top;i++){ 68 e[trace[i]].c -= tf; 69 e[trace[i]^1].c += tf; 70 } 71 flow += tf; 72 u = e[trace[ins]].u, top = ins; 73 } 74 if(u != sink && gap[dep[u]-1]==0) break; 75 for(i=cur[u];i!=-1;i=next[i]) 76 if(e[i].c > 0 && dep[u] == dep[e[i].v] + 1) 77 break; 78 if(i != -1) { 79 trace[top++] = i; 80 cur[u] = i; 81 u = e[i].v; 82 } 83 else { 84 int mindep = maxdep; 85 for(i=head[u];i!=-1;i=next[i]){ 86 if(e[i].c && dep[e[i].v] < mindep) 87 mindep = dep[e[i].v], cur[u] = i; 88 } 89 gap[dep[u]]--; 90 dep[u] = mindep + 1; 91 gap[dep[u]]++; 92 if(u != source) 93 u = e[trace[--top]].u; 94 } 95 } 96 return flow; 97 } 98 //**********************************// 99 int in[maxn],out[maxn],du[maxn],basement; 100 int lownm[370][1010]; 101 int order[370][1010],oidx[370]; 102 void initial() 103 { 104 cnt = 0; 105 memset(head,-1,sizeof(head)); 106 memset(in,0,sizeof(in)); 107 memset(out,0,sizeof(out)); 108 memset(lownm,0,sizeof(lownm)); 109 //initial source ,sink and maxdep; 110 } 111 int main() 112 { 113 int n,m; 114 while(scanf("%d%d",&n,&m) != EOF){ 115 initial(); 116 source = n+m+8; 117 sink = source+1; 118 maxdep = sink+2; 119 int ss=n+m+1; 120 int tt=ss+1; 121 int fsum = 0; 122 basement = tt; 123 for(int i=0;i<m;i++) 124 scanf("%d",&out[i+n]), in[tt]+=out[i+n], add(i+n,tt,maxf-out[i+n]); 125 int c,d; 126 for(int nn=0;nn<n;nn++){ 127 scanf("%d%d",&c,&d); 128 oidx[nn] = c; 129 add(ss,nn,d); 130 int girl,low,up; 131 for(int cc=0;cc<c;cc++){ 132 scanf("%d%d%d",&girl,&low,&up); 133 lownm[nn][girl]=low; 134 add(nn,n+girl,up-low); 135 out[nn]+=low; 136 in[n+girl] += low; 137 order[nn][cc] = girl; 138 } 139 } 140 int fcnt = cnt; 141 add(tt,ss,maxf); 142 int sum = 0; 143 for(int i=0;i<=basement;i++){ 144 du[i] = in[i]-out[i]; 145 if(du[i] > 0) add(source,i,du[i]), sum+=du[i]; 146 else if(du[i] < 0) add(i,sink,-du[i]); 147 } 148 int flow = maxF(); 149 if(flow < sum) printf("-1 "); 150 else { 151 source = ss; 152 sink = tt; 153 maxdep = sink+2; 154 //e[fcnt].c = 0, e[fcnt^1] = 0; 155 flow = maxF(); 156 for(int i=0;i<n;i++) 157 for(int j=head[i];j>=0;j=next[j]) 158 if(!(j&1)) 159 lownm[i][e[j].v-n] += e[j^1].c; 160 //flow = 0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) flow += lownm[i][j]; 161 printf("%d ",flow); 162 for(int i=0;i<n;i++) 163 for(int j=0;j<oidx[i];j++) 164 printf("%d ",lownm[i][order[i][j]]); 165 puts(""); 166 } 167 } 168 return 0; 169 }
另外在贴上一个未AC的代码，这个代码错在构图，***调了我8个小时，还是没搞定。。。
我当时的构图思路是这样的： source --> 某个女神 --> 某一天 --> 汇点。结果就弹了一天。
后来AC代码改成：source --> 某一天 --> 某个女神--> 汇点。很怀疑是这个special judge的判题程序弱爆了。请有能力的大神给我指点迷津啊。。。
代码如下，请大神斧正！
1 /* 2 构图。。。不解，未AC 3 */ 4 #include <iostream> 5 #include <cstring> 6 #include <cstdio> 7 using namespace std; 8 const int maxn = 1500; 9 const int maxe = 1001001; 10 const int maxf = (-1)^(1<<31); 11 #define smaller(a,b) ((a)<(b)?(a):(b)) 12 struct edge{ 13 int u,v,c; 14 edge(int a=0,int b=0,int d=0){ u=a, v=b, c=d; } 15 }e[maxe]; 16 int head[maxn]; 17 int next[maxe]; 18 int cnt; 19 void add(int u,int v,int c){ 20 e[cnt] = edge(u,v,c); 21 next[cnt] = head[u], head[u] = cnt++; 22 //printf("cnt = %d, %d --> %d with c = %d, next = %d ",cnt-1,u,v,c,next[cnt-1]); 23 e[cnt] = edge(v,u,0); 24 next[cnt] = head[v], head[v] = cnt++; 25 } 26 //***********************************// 27 int source,sink,maxdep; 28 int dep[maxn],gap[maxn]; 29 int cur[maxn],trace[maxn],que[maxn],top; 30 void setGD(){ 31 for(int i=0;i<=maxdep;i++) dep[i] = maxdep; 32 dep[sink] = 0; 33 int front,rear,u,v; 34 front = rear = 0; 35 que[rear++] = sink; 36 while(front != rear){ 37 u = que[front++]; 38 if(front >= maxn) front = 0; 39 for(int i=head[u];i!=-1;i=next[i]){ 40 v = e[i].v; 41 if(v > maxdep) continue; 42 if(dep[v] < maxdep) continue; //if(e[i].c || dep[v] <= dep[u]+1) continue; //不是逆向边，或者'被访问过' 43 dep[v] = dep[u]+1; 44 que[rear++] = v; 45 if(rear >= maxn) rear = 0; 46 } 47 } 48 memset(gap,0,sizeof(gap)); 49 for(int i=0;i<=maxdep;i++) gap[dep[i]]++; 50 } 51 int maxF(){ 52 setGD(); 53 for(int i=0;i<=maxdep;i++) cur[i] = head[i]; 54 int u=source,flow=0,i; 55 top = 0; 56 while(dep[source] <= maxdep){ 57 if(u == sink){ 58 int tf = maxf,ins; 59 for(i=0;i<top;i++){ //找瓶颈边 60 if(tf > e[trace[i]].c){ 61 tf = e[trace[i]].c; 62 ins = i; 63 } 64 } 65 /* 66 for(i=0;i<top;i++) 67 printf("%d -> ",e[trace[i]].u); 68 printf("%d , temp_flow = %d ",e[trace[top-1]].v,tf); 69 */ 70 for(i=0;i<top;i++){ 71 e[trace[i]].c -= tf; 72 e[trace[i]^1].c += tf; 73 } 74 flow += tf; 75 u = e[trace[ins]].u, top = ins; 76 } 77 if(u != sink && gap[dep[u]-1]==0) break; 78 for(i=cur[u];i!=-1;i=next[i]) 79 if(e[i].c > 0 && dep[u] == dep[e[i].v] + 1) 80 break; 81 if(i != -1) { 82 trace[top++] = i; 83 cur[u] = i; 84 u = e[i].v; 85 } 86 else { 87 int mindep = maxdep; 88 for(i=head[u];i!=-1;i=next[i]){ 89 if(e[i].c && dep[e[i].v] < mindep) 90 mindep = dep[e[i].v], cur[u] = i; 91 } 92 gap[dep[u]]--; 93 dep[u] = mindep + 1; 94 gap[dep[u]]++; 95 if(u != source) 96 u = e[trace[--top]].u; 97 } 98 } 99 return flow; 100 } 101 //**********************************// 102 int in[maxn],out[maxn],du[maxn],basement; 103 int lownm[370][1010]; 104 int order[370][1010],oidx[370]; 105 void initial() 106 { 107 cnt = 0; 108 memset(head,-1,sizeof(head)); 109 memset(in,0,sizeof(in)); 110 memset(out,0,sizeof(out)); 111 memset(lownm,0,sizeof(lownm)); 112 //initial source ,sink and maxdep; 113 } 114 int main() 115 { 116 int n,m; 117 while(scanf("%d%d",&n,&m) != EOF){ 118 initial(); 119 source = n+m+8; 120 sink = source+1; 121 maxdep = sink+2; 122 int ss=n+m+1; 123 int tt=ss+1; 124 int fsum = 0; 125 basement = tt; 126 for(int i=0;i<m;i++) 127 scanf("%d",&in[i]), out[ss]+=in[i], add(ss,i,maxf), fsum+=in[i]; 128 int c,d; 129 for(int nn=0;nn<n;nn++){ 130 scanf("%d%d",&c,&d); 131 oidx[nn] = c; 132 int girl,low,up; 133 for(int cc=0;cc<c;cc++){ 134 scanf("%d%d%d",&girl,&low,&up); 135 lownm[nn][girl]=low; 136 add(girl,m+nn,up-low); 137 out[girl]+=low; 138 in[m+nn] +=low; 139 order[nn][cc] = girl; 140 } 141 add(m+nn,tt,d); 142 } 143 int fcnt = cnt; 144 add(tt,ss,maxf); 145 int sum = 0; 146 for(int i=0;i<=basement;i++){ 147 du[i] = in[i]-out[i]; 148 if(du[i] > 0) add(source,i,du[i]), sum+=du[i]; 149 else if(du[i] < 0) add(i,sink,-du[i]); 150 } 151 int flow = maxF(); 152 int flag = 1; 153 for(int i=head[source];i>=0;i=next[i]) 154 if(e[i].c){ 155 flag = 0; 156 break; 157 } 158 if(!flag) printf("-1 "); 159 else { 160 source = ss; 161 sink = tt; 162 maxdep = sink+2; 163 //e[fcnt].c = 0, e[fcnt^1] = 0; 164 flow = maxF(); 165 for(int i=n+m;i>=m;i--) 166 for(int j=head[i];j>=0;j=next[j]) 167 if(j&1) 168 lownm[i-m][e[j].v] += e[j].c; 169 //flow = 0; for(int i=0;i<n;i++) for(int j=0;j<m;j++) flow += lownm[i][j]; 170 printf("%d ",flow); 171 for(int i=0;i<n;i++) 172 for(int j=0;j<oidx[i];j++) 173 printf("%d ",lownm[i][order[i][j]]); 174 puts(""); 175 } 176 } 177 return 0; 178 }