上下界的网络流

对于一条边，考虑分离下界流量和可行流，则应从起点将下界流出，而从终点再将下界流入，其本身容量量应为其上界减下界所得容量，即可行流。

因此可以新建超级源汇，分别对每一条边的起点和终点连出如上所述的边。考虑一个点不用多次连边，故可以合并，即统计每个点分离的下界流量（出或入），再统一连边。对于原源汇，为了使其满足流量平衡条件，应从汇向源连一条容量为无穷大的边。最后求出超级源汇的最大流，若代表下界的边满流，则存在可行流。因此只需对于残量网络继续增广求出最大流就是满足上下界约束条件的最大流。

为了加速，可以考虑删去从汇向源连出的边，但是此时答案是超级源汇的最大流与残量网络最大流的和，因为超级源汇最大流代表满足下界所必须的流量，是答案的一部分。

Code:

#include <cstdio>#include <cmath>#include <cstdlib>#include <cstring>#include <ctime>#include <cctype>#include <vector>#include <map>#include <set>#include <algorithm>using namespace std;#ifdef WIN32#define fmt64 "%I64d"#else#define fmt64 "%lld"#endif#define PI M_PI#define oo 0x13131313#define iter iterator#define PB push_back#define MP make_pair#define fst first#define snd second#define FOR(i, j, k) for (i = (j); i <= (k); ++i)#define ROF(i, j, k) for (i = (j); i >= (k); --i)#define FER(i, j, k) for (i = j[k]; i; i = i->n)typedef unsigned int uint;typedef long long int64;typedef unsigned long long uint64;typedef long double real;template<class T> inline bool minim(T &a, const T &b) {return b < a ? a = b, 1 : 0;}template<class T> inline bool maxim(T &a, const T &b) {return b > a ? a = b, 1 : 0;}template<class T> inline T sqr(const T &a) {return a * a;}#define maxm 1000005#define maxn 1010#define dual(e) (es + (((e) - es) ^ 1))struct edge {int s, t, f; edge *n;} es[maxm], *adj = es + 1, *lst[maxn];int n, m, K, S, T, S0, S1, T1;int sum[maxn][maxn], num[maxn][maxn];int dis[maxn], q[maxn];int out[maxn]; edge *pre[maxn], *back;namespace dinic{int S, T, flow, temp;bool bfs(){int ll, rr; edge *e;memset(dis, -1, sizeof dis), dis[T] = 0;q[ll = rr = T] = 0;for (; ll; ll = q[ll])FER(e, lst, ll) if (dual(e)->f && !~dis[e->t])dis[e->t] = dis[ll] + 1, q[rr = q[rr] = e->t] = 0;return ~dis[S];}int extend(){int res, f = oo;for (int i = T; i != S; i = pre[i]->s) if (minim(f, pre[i]->f)) res = pre[i]->s;for (int i = T; i != S; i = pre[i]->s) pre[i]->f -= f, dual(pre[i])->f += f;flow += f;return res;}int dfs(int u){edge *e;if (u == T) return extend();FER(e, lst, u) if (e->f && dis[e->t] == dis[u] - 1) {pre[e->t] = e, temp = dfs(e->t);if (~temp && temp != u) return temp;}return dis[u] = -1;}int main(int SS, int TT){S = SS, T = TT, flow = 0;for (; bfs(); )dfs(S);return flow;}}void link(int u, int v, int L, int R){*(++adj) = (edge){u, v, R - L, lst[u]}, lst[u] = adj;*(++adj) = (edge){v, u,     0, lst[v]}, lst[v] = adj;out[u] += L, out[v] -= L;}void link_all(){S1 = T + 1, T1 = S1 + 1;for (int i = 1; i <= T; ++i)if (out[i])out[i] > 0 ? link(i, T1, 0, out[i]) : link(S1, i, 0, -out[i]);}void init(){int i, j, k;scanf("%d%d%d", &n, &m, &K);S0 = n + m + 1, S = S0 + 1, T = S + 1;link(T, S, 0, oo), back = adj;link(S, S0, 0, K);FOR(i, 1, n) {int C, *s = sum[i];scanf("%d", &C);FOR(j, 1, C) scanf("%d", &k), ++s[k];}int F;for (scanf("%d", &F); F--; ) {int A, B;scanf("%d%d", &A, &B);++num[A][B];}FOR(i, 1, n) {int *t = num[i], *s = sum[i];FOR(j, 1, m) if (s[j])link(i, n + j, t[j], s[j]);}FOR(i, 1, m) {int A;scanf("%d", &A);link(n + i, T, 0, A);}FOR(i, 1, n) {int L, R;scanf("%d%d", &R, &L);link(S0, i, L, R);}link_all();}int main(){freopen("underground.in", "r", stdin);freopen("underground.out", "w", stdout);init();int ans = dinic::main(S1, T1);back->f = 0;ans += dinic::main(S, T);printf("%d\n", ans);return 0;}