有上下界的网络流专辑
相对于一般的网络流，有上下界的网络流的某些边多出了流量下界的限制，如边u->v，上下界为high、low，如果有流经过这条边，这个流必须在[low，high]这个区间内。这类题目主要要求解决下面三个问题，“有源汇、无源汇的可行流”、“有源汇的最大流”、“有源汇的最小流”，注意这里所说的源汇是原网络中的源汇，分别记为s、t。 这类题目的难点在于下界的限制很难处理，我们将所有有下界限制的边中分离出“必须边”来单独做考虑，所谓“必须边”就是必须要满流的边，如上述的边，我们可以拆成两条边，第一条是“必须边”，流量上限为low，第二条是一般的边，流量上限为high-low。 怎样对必须边进行考虑呢？我们建立新的超级源汇，记为ss、tt，对于所有必须边再次进行拆边处理，如上述必须边u->v，应该拆成ss->v、u->tt两条流量上限都为low的边（这里很重要，应该要好好理解，我当时学的时候是不断画图来体会这种思想的）。 经过上述步骤，我们所需要的网络已经建立好了，依次来分析那三个问题。（这里所提到的所有变量均为上面所定义的） 一、有源汇、无源汇的可行流。 求可行流，其实就是问是否存在一个方案可以使所有必须边都满流。对于有源汇的网络，我们可以添加一条边t->s，流量上限为INF，这样就变成了无源汇的网络。对于无源汇的网络，只要对ss到tt求一次最大流，若所有必须边都满流，则有可行解，若要求打印方案，只需将非必须边中流过的流量加上流量下界（必须边已满流）。 二、有源汇的最大流 这里的最大流，前提是使所有必须边满流，再要求从s到t的流量最大（注意，这里所求的最大流是原网络的最大流，而我们求ss到tt的最大流只是用于判断是否能使所有必须边满流）。首先判断所有必须边是否满流，这里和问题一中提到的方法一样，注意这里是有源汇的网络。然后直接对残留网络求一次从s到t的最大流，这个最大流就是最终答案。 三、有源汇的最小流 和问题二相反，我们要使所有必须边满流的情况下，要求从s到t的流量最小。这个问题比上面的问题都要复杂，分三个步骤。1、对ss到tt求一次最大流，记为f1。（在有源汇的情况下，先使整个网络趋向必须边尽量满足的情况）2、添加一条边t->s，流量上限为INF，这条边记为p。（构造无源汇网络）3、对ss到tt再次求最大流，记为f2。（要判断可行，必须先构造无源汇网络流，因此要再次求最大流） 如果所有必须边都满流，证明存在可行解，原图的最小流为“流经<边p>的流量”（原图已构造成无源汇网络，对于s同样满足入流 == 出流，只有新添加的边流向s，而s的出流就是原图的最小流）。
这类题目的建模难度都很小，几乎可以一眼看出网络流模型，主要是构图、求解方面的问题，这里贴出我找到的仅有的6道题目的核心代码，所有求最大流都是用Dinic，这里为了尽量简洁略去Dinic的实现。然后题意、类型、题解也不写了，认真读完上面的讲解已经足够解决以下问题。
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2314 ZOJ 2314
// 1790 Ms#include <iostream>#include <cstring>#include <cstdio>#include <queue>using namespace std;const int INF = 1e9;const int N = 2010;const int M = 500*N; // N*N 会MLE，100*N 会RE，500*N 刚好AC struct Data{ int x, y, f, next;} edge[M];int inx;int node[N], level[N]; void addedge(int u, int v, int f){ edge[inx].x = u, edge[inx].y = v, edge[inx].f = f; edge[inx].next = node[u], node[u] = inx++; edge[inx].x = v, edge[inx].y = u, edge[inx].f = 0; edge[inx].next = node[v], node[v] = inx++;} int main(){ int n, m; while (scanf("%d %d", &n, &m) != EOF) { inx = 0; memset(node, -1, sizeof(node)); int s = n+m+10, t = s+1; int ss = t+1, tt = ss+1; int sum = 0; queue< pair<int, int> > que; int a, b, c; for (int i = 0; i < m; i++) { scanf("%d", &a); addedge(i, tt, a); addedge(ss, t, a); sum += a; addedge(i, t, INF); // 每个女孩拍照下限为ai，上限为INF } for (int i = 1; i <= n; i++) { int C, D; scanf("%d %d", &C, &D); addedge(s, m+i, D); // 每天最多拍照数为D for (int j = 1; j <= C; j++) { scanf("%d %d %d", &a, &b, &c); addedge(m+i, tt, b); addedge(ss, a, b); sum += b; que.push(make_pair(b, inx)); addedge(m+i, a, c-b); // 该天a女孩拍照下限为b，上限为c } } addedge(t, s, INF); // 求有上下界的最大流 int flow = Dinic(ss, tt); if (sum != flow) printf("-1\n"); else { printf("%d\n", Dinic(s, t)); while ( !que.empty() ) { int down = que.front().first; int p = que.front().second; printf("%d\n", down + edge[p^1].f); que.pop(); } } printf("\n"); } return 0;}