学习日志|有上下界的网络流学习日志|网络流

上下界网络流，大致思路是虚拟超级源点和汇点(ss&tt)，让每个点的流量底线强行用超级源点和超级汇点来满足。
具体来讲，分为无源汇（求循环流），有源汇（求满足限制的最大流、最小流）。
具体原理不想写了，实现的时候求最大流有两种写法：用ss&tt先跑一次，然后删ss和tt在利用原来的s和t跑一次两者加起来，或者不删点直接再跑一次s和t的最大流。当然二分什么的就不说了，太慢了。
作业里大部分是模板题，我挑重点说吧。
zooj3229 shoot the bullet 题目本身很裸，看了题目就知道怎么建图了，但是调试很恶心。网络流的题实在不好调，不像数据结构题那样比较有针对性。昨晚熬夜调到一点半，结果发现问题是求最大流的时候网络流作用域里面的顶点数没有修改，就跪烂了。。这是比较有意义的一个地方，就是因为sap算法里面距离标号和顶点数关系很大，所以要时刻保证你记录顶点数cnt不能少（可以稍微多一点），不然就容易提前退出了，花了大半天的时间发现这个问题还是值得。
poj2396 budget 好题。我已开始想把n*m个数全部建成点，结果发现好像图就太大了。。然后看了下别人的建图方法，把行作为x部，列作为y部，用边来表示数，挺科学的。
zoj3496 assignment 好题。一开始题目看了半天没看懂，然后就去找了，看了中文题目发现不知道怎么想。然后看了题解，确实很科学。首先贪心地，如果你想要让收费尽量多或者尽量少，就要将所有技能点放在同一条边上。同时涉及了一点博弈的思路，别人肯定是尽力想坑你的钱，所以肯定是想按上述贪心规则来。你要让别人坑你钱坑得尽量少，你就要将自己的缺点藏好，也就是让你的流网络中最大流量的边尽量小。想到这里，就明显是二分答案了。二分边的上限即可。另一个子问题，类似地，是让最小流量的边尽量大，这就要设置下限，需要加超级源点和汇点来限流了。
【学习日志|有上下界的网络流】这道题确实不错，没有像其他二分答案的题一样很裸的告诉你要最小化最大值，而是要连续转几个弯。
这道题今天也调了我很久，最后发现原来是我的程序不兹瓷空图的情况。。害的我今天晚上又没睡好觉，我真是想砍人，这种摆明了坑人的数据真不知道有什么意思！我（&*%￥%*#@-^*+）你的出题人！以后做ACM的题要注意这种坑爹的地方，上学期模板检测就是一个坑爹的n=0的数据害得我抄了十遍代码。以后ACM题第一步特判。

update：上下界网络流码量真不少。经过几道题总结出了封装好的模板。

struct Ed { int to, cap, flow, lb; Ed *nxt, *back; }; struct FlowNet { #define clr(a) memset(a,0,sizeof a) #define rep(i,a,b) for(int i=a; i<=b; ++i) int S, T, vn; int in[MAXN], out[MAXN]; int d[MAXN], vd[MAXN]; Ed Edge[MAXM], *ecnt, *adj[MAXN]; FlowNet() { ecnt=Edge; } void init(int a, int b, int c) { clr(adj), clr(in), clr(out); ecnt = Edge; vn = a; S = b; T = c; } inline void adde(int a, int b, int L, int R) { (++ecnt)->to = b; ecnt->cap = R - L; ecnt->flow = 0; ecnt->nxt = adj[a]; ecnt->lb = L; adj[a] = ecnt; ecnt->back = ecnt+1; (++ecnt)->to = a; ecnt->cap = 0; ecnt->flow = 0; ecnt->nxt = adj[b]; adj[b] = ecnt; ecnt->back = ecnt-1; } inline void sete(int a, int b, int L, int R) { adde(a, b, L, R); in[b] += L, out[a] += L; } int aug(int u, int augco) { if (u == T) return augco; int augc = augco, delta, mind=vn-1; for (Ed*p = adj[u]; p; p=p->nxt) { if (p->flow >= p->cap) continue; if (d[p->to]+1 == d[u]) { delta = aug(p->to, min(augc, p->cap - p->flow)); augc -= delta; p->flow += delta, p->back->flow -= delta; if (d[S] == vn) return augco - augc; if (!augc) break; } mind = min(mind, d[p->to]); } if (augc==augco) { if (!--vd[d[u]]) d[S] = vn; ++vd[d[u] = mind+1]; } return augco - augc; } int ISAP() { int flow = 0; clr(d); clr(vd); vd[0] = vn; while (d[S] < vn) flow += aug(S, inf); return flow; } bool check() { int cntc = 0, cntf = 0; for (Ed*p = adj[S]; p; p=p->nxt) cntc += p->cap, cntf += p->flow; return cntc == cntf; } void rebuild(int &ss, int &tt) { ss = vn+1, tt = vn+2; rep(i, 1, vn) if (in[i] > out[i]) adde(ss, i, 0, in[i] - out[i]); else adde(i, tt, 0, out[i] - in[i]); vn += 3; } int maxflow() { int ss, tt, s1 = S, t1 = T; rebuild(ss, tt); adde(t1, s1, 0, inf); S = ss, T = tt; ISAP(); if (!check()) return -1; S = s1, T = t1; return ISAP(); } int minflow() { int ss, tt, s1 = S, t1 = T; rebuild(ss, tt); S = ss, T = tt; ISAP(); adde(t1, s1, 0, inf); return ISAP(); } } G;

指针版的网络流显得比较冗长，以下是数组版的上下界网络流模板。

struct Ed { int to, c, flow, lb, nxt; }; struct FlowNet { int S, T, vn, ec; int in[MAXN], out[MAXN]; int d[MAXN], vd[MAXN], adj[MAXN]; Ed e[MAXM]; void init(int a, int b, int c) { clr(in), clr(out); memset(adj, -1, sizeof adj); ec = 0; vn = a; S = b; T = c; } inline void adde(int a, int b, int L, int R) { e[ec].to = b; e[ec].c = R - L; e[ec].nxt = adj[a]; e[ec].lb = L; adj[a] = ec++; e[ec].to = a; e[ec].c = 0; e[ec].nxt = adj[b]; adj[b] = ec++; } inline void sete(int a, int b, int L, int R) { adde(a, b, L, R); in[b] += L, out[a] += L; } int aug(int u, int augco) { if (u == T) return augco; int augc = augco, delta, mind=vn-1, v; for (int i=adj[u]; ~i; i=e[i].nxt) { if (e[i].c<=0) continue; v = e[i].to; if (d[v]+1 == d[u]) { delta = aug(v, min(augc, e[i].c)); augc -= delta; e[i].c -= delta, e[i^1].c += delta; if (d[S] == vn) return augco - augc; if (!augc) break; } mind = min(mind, d[v]); } if (augc==augco) { if (!--vd[d[u]]) d[S] = vn; ++vd[d[u] = mind+1]; } return augco - augc; } int sap() { int flow = 0; clr(d); clr(vd); vd[0] = vn; while (d[S] < vn) flow += aug(S, inf); return flow; } bool check() { for (int i = adj[S]; ~i; i=e[i].nxt) if (e[i].c > 0) return 0; return 1; } void rebuild(int &ss, int &tt) { ss = vn+1, tt = vn+2; rep(i, 1, vn) if (in[i] > out[i]) adde(ss, i, 0, in[i] - out[i]); else adde(i, tt, 0, out[i] - in[i]); vn += 3; } int maxflow() { int ss, tt, s1 = S, t1 = T; rebuild(ss, tt); sete(t1, s1, 0, inf); S = ss, T = tt; sap(); if (!check()) return -1; S = s1, T = t1; return sap(); } int minflow() { int ss, tt, s1 = S, t1 = T; rebuild(ss, tt); S = ss, T = tt; sap(); sete(t1, s1, 0, inf); return sap(); } } G;