• 已经 2 周没写博客了
• 这也是 2019 的第一篇博客，一个新的开始

引入

• 最小割的概念：给定一个图，含源点 $S$ 和汇点 $T$ ，每条有向边有容量
• 选出一些边删掉，使得没有从 $S$ 到 $T$ 的路径
• 求选出的边的容量和的最小值
• 最大流和最小割都是线性规划问题中的一类
• 最小割可以看成是最大流的对偶问题
• 定理：最大流 $=$ 最小割
• 证明
• 显然最小割不能小于最大流
• 我们知道，跑完最大流之后，残余网络中没有从 $S$ 到 $T$ 的路径
• 图被分为两个集合
• 根据流量平衡条件得到，流出 $S$ 所在集合的流量等于流入 $T$ 所在集合的流量
• 而横跨 $S$ 所在集合和 $T$ 所在集合的所有边构成一个割，且等于最大流
• 于是这个割就是最小割
• 证毕
• 最小割在题目中最常见的模型就是互斥选择模型（有这个模型更好的定义请在评论区指出）
• 例如： $n$ 个变量，每个变量取 $0$ 有一定代价，取 $1$ 有一定代价，外加 $m$ 个约束 $(i,j,x)$ ，表示 $i$ 和 $j$ 取不同值有额外代价 $x$ ，求最小代价和
• 下面我在 BZOJ 上选出了 $10$ 道最小割题
• 这 $10$ 道题都是互斥选择的模型

（1）[BZOJ1943][Shoi2007]Vote 善意的投票

题意

• 即为引入中举的栗子
• $n$ 个变量，第 $i$ 个变量为 x i x_i xi​
• 当 x i x_i xi​ 取值等于 a i a_i ai​ 时不产生代价，否则产生 $1$ 的代价
• 有 $m$ 个二元组 $(i,j)$
• 表示 $(i,j)$ 取值不同则会产生 $1$ 的代价
• 求最小代价和
• $2\le n\le 300$

做法

• 源点 $S$ 汇点 $T$
• 对于所有的 $1\le i\le n$ ，对第 $i$ 个变量 x i x_i xi​ 建点 $i$
• 如果 a i = 0 a_i=0 ai​=0
• 则由 $S$ 向 $i$ 连容量为 $1$ 的边
• 由 $i$ 向 $T$ 连容量为 $0$ 的边
• 否则由 $S$ 向 $i$ 连容量为 $0$ 的边
• $i$ 向 $T$ 连容量为 $1$ 的边
• 这时候边 $<S,i>$ 和 $<i,T>$ 显然有且仅有一条边被割掉
• 可以看成如果保留边 $<S,i>$ 则 x i x_i xi​ 取 $0$
• 否则 x i x_i xi​ 取 $1$
• 考虑处理变量间的影响
• 对于二元组 $(i,j)$ ，连边 $<i,j>$ 和 $<j,i>$ ，容量都为 $1$
• 这样的含义是，如果保留了边 $<S,i>$ 和 边 $<j,T>$ ，那么还需要额外割掉边 $<i,j>$ ，否则存在一条 $S$ 到 $T$ 的路径 $S->i->j->T$
• $<j,i>$ 同理
• 实际上容量为 $0$ 的边没必要建，在上面只是为了便于理解而建出来
• 求一遍最小割即为答案
• 此外，如果二元组 $(i,j)$ 是限制 x i x_i xi​ 必须等于 x j x_j xj​ ，则只需要把 $<i,j>$ 和 $<j,i>$ 的容量设为 $\infty$ （表示该边割不掉）即可

代码

#include 
#include 
#include 
#include 
#include 
#define For(i, a, b) for (i = a; i <= b; i++)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
#define NF(u) for (int &e = cur[u], v = go[e]; e; e = nxt[e], v = go[e])inline int read()
{int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}const int N = 610, M = 6e5 + 5, INF = 0x3f3f3f3f;int n, m, ecnt = 1, nxt[M], adj[N], go[M], cap[M], S, T, lev[N],
len, que[N], cur[N], ans;void add_edge(int u, int v, int w)
{nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; cap[ecnt] = w;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u; cap[ecnt] = 0;
}bool bfs()
{int i;For (i, S, T) cur[i] = adj[i], lev[i] = -1;lev[que[len = 1] = S] = 0;For (i, 1, len){int u = que[i];Edge(u) if (cap[e] && lev[v] == -1){lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}int dinic(int u, int flow)
{if (u == T) return flow;int res = 0, delta;NF(u) if (cap[e] && lev[u] < lev[v]){delta = dinic(v, Min(cap[e], flow - res));if (delta){cap[e] -= delta; cap[e ^ 1] += delta;res += delta; if (res == flow) break;}}if (res != flow) lev[u] = -1;return res;
}int main()
{int i, x, y;n = read(); m = read();S = 1; T = n + 2;For (i, 1, n){x = read();if (x) add_edge(1 + i, T, 1);else add_edge(S, 1 + i, 1);}while (m--) x = read(), y = read(),add_edge(x + 1, y + 1, 1), add_edge(y + 1, x + 1, 1);while (bfs()) ans += dinic(S, INF);std::cout << ans << std::endl;return 0;
}

（2）[BZOJ2127]happiness

题意

• $n\times m$ 的变量矩阵 x i , j x_{i,j} xi,j​
• 对于任意的 $1\le i\le n,1\le j\le m$
• 如果 x i , j = 0 x_{i,j}=0 xi,j​=0 则有 a i , j a_{i,j} ai,j​ 的收益
• 如果 x i , j = 1 x_{i,j}=1 xi,j​=1 则有 b i , j b_{i,j} bi,j​ 的收益
• 对于每个相邻（有且仅有一条公共边）的格子 $(i,j)$ $(u,v)$
• 如果 x i , j = x u , v = 0 x_{i,j}=x_{u,v}=0 xi,j​=xu,v​=0 则有 c i , j , u , v c_{i,j,u,v} ci,j,u,v​ 的收益
• 如果 x i , j = x u , v = 1 x_{i,j}=x_{u,v}=1 xi,j​=xu,v​=1 则有 d i , j , u , v d_{i,j,u,v} di,j,u,v​ 的收益
• $n,m\le 100$ ， 0 ≤ a i , j , b i , j , c i , j , u , v , d i , j , u , v ≤ 5000 0\le a_{i,j},b_{i,j},c_{i,j,u,v},d_{i,j,u,v}\le 5000 0≤ai,j​,bi,j​,ci,j,u,v​,di,j,u,v​≤5000

做法

• 转化问题
• 如果 x i , j = 0 x_{i,j}=0 xi,j​=0 则有 b i , j b_{i,j} bi,j​ 的代价
• 如果 x i , j = 1 x_{i,j}=1 xi,j​=1 则有 a i , j a_{i,j} ai,j​ 的代价
• 对于每个相邻（有且仅有一条公共边）的格子 $(i,j)$ $(u,v)$
• 如果 $(i,j)=0$ 或 $(u,v)=0$ 则有 d i , j , u , v d_{i,j,u,v} di,j,u,v​ 的代价
• 如果 $(i,j)=1$ 或 $(u,v)=1$ 则有 c i , j , u , v c_{i,j,u,v} ci,j,u,v​ 的代价
• 求
• $$\sum a+\sum b+\sum c+\sum d-最小代价和$$
• 发现与上一题不同的地方就在于 c 和 d 不相等
• 所以我们考虑设
• p i , j = a i , j + ∑ i ≤ u , j ≤ v c i , j , u , v p_{i,j}=a_{i,j}+\sum_{i\le u,j\le v}c_{i,j,u,v} pi,j​=ai,j​+i≤u,j≤v∑​ci,j,u,v​
• q i , j = b i , j + ∑ i ≤ u , j ≤ v d i , j , u , v q_{i,j}=b_{i,j}+\sum_{i\le u,j\le v}d_{i,j,u,v} qi,j​=bi,j​+i≤u,j≤v∑​di,j,u,v​
• 由 $S$ 向点 $(i,j)$ 连容量为 p i , j p_{i,j} pi,j​ 的边
• 点 $(i,j)$ 向 $T$ 连容量为 q i , j q_{i,j} qi,j​ 的边
• 对于每个 $(i,j,u,v)$ （ $i\le u,j\le v$ ）
• 由点 $(i,j)$ 向点 $(u,v)$ 连容量为 c i , j , u , v c_{i,j,u,v} ci,j,u,v​ 的边
• 由点 $(u,v)$ 向点 $(i,j)$ 连容量为 d i , j , u , v d_{i,j,u,v} di,j,u,v​ 的边
• 为了得出正确性，对两个相邻点 $(i,j)$ $(u,v)$ （ $i\le u,j\le v$ ）进行一波讨论
• 如果两个变量都取 $0$ ，那么必然导致 $<(i,j),T>$ 和 $<(u,v),T>$ 被割掉
• 产生的代价为
• b i , j + b u , v + d i , j , u , v b_{i,j}+b_{u,v}+d_{i,j,u,v} bi,j​+bu,v​+di,j,u,v​
• 都取 $1$ 同理
• 如果 x i , j x_{i,j} xi,j​ 取 $0$ 而 x u , v x_{u,v} xu,v​ 取 $1$ ，则必然导致边 $<S,(u,v)>$ $<(i,j),(u,v)>$ $<(i,j),T>$ 被割掉
• 产生的代价为
• b i , j + a u , v + d i , j , u , v + c i , j , u , v b_{i,j}+a_{u,v}+d_{i,j,u,v}+c_{i,j,u,v} bi,j​+au,v​+di,j,u,v​+ci,j,u,v​
• 联合上 p i , j p_{i,j} pi,j​ 和 q i , j q_{i,j} qi,j​ 的定义，就容易得出正确性

代码

#include 
#include 
#include 
#include 
#include 
#define For(i, a, b) for (i = a; i <= b; i++)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
#define NF(u) for (int &e = cur[u], v = go[e]; e; e = nxt[e], v = go[e])inline int read()
{int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}const int E = 105, N = 1e4 + 10, M = 12e4 + 12, INF = 0x3f3f3f3f;int n, m, a[E][E], b[E][E], ecnt = 1, S, T, nxt[M], adj[N], go[M], cap[M],
len, que[N], lev[N], cur[N], c[E][E], d[E][E], s[E][E], t[E][E];int which(int x, int y) {return (x - 1) * m + y + 1;}void add_edge(int u, int v, int w)
{nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; cap[ecnt] = w;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u; cap[ecnt] = 0;
}bool bfs()
{int i;For (i, S, T) lev[i] = -1, cur[i] = adj[i];lev[que[len = 1] = S] = 0;For (i, 1, len){int u = que[i];Edge(u) if (cap[e] && lev[v] == -1){lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}int dinic(int u, int flow)
{if (u == T) return flow;int res = 0, delta;NF(u) if (cap[e] && lev[u] < lev[v]){delta = dinic(v, Min(cap[e], flow - res));if (delta){cap[e] -= delta; cap[e ^ 1] += delta;res += delta; if (res == flow) break;}}if (res != flow) lev[u] = -1;return res;
}int maxflow()
{int res = 0;while (bfs()) res += dinic(S, INF);return res;
}int main()
{int i, j, x, sum = 0;n = read(); m = read();S = 1; T = n * m + 2;For (i, 1, n) For (j, 1, m) sum += (a[i][j] = read());For (i, 1, n) For (j, 1, m) sum += (b[i][j] = read());For (i, 1, n - 1) For (j, 1, m)a[i][j] += (c[i][j] = x = read()), sum += x;For (i, 1, n - 1) For (j, 1, m)b[i][j] += (d[i][j] = x = read()), sum += x;For (i, 1, n) For (j, 1, m - 1)a[i][j] += (s[i][j] = x = read()), sum += x;For (i, 1, n) For (j, 1, m - 1)b[i][j] += (t[i][j] = x = read()), sum += x;For (i, 1, n) For (j, 1, m)add_edge(S, which(i, j), a[i][j]),add_edge(which(i, j), T, b[i][j]);For (i, 1, n - 1) For (j, 1, m)add_edge(which(i, j), which(i + 1, j), c[i][j]),add_edge(which(i + 1, j), which(i, j), d[i][j]);For (i, 1, n) For (j, 1, m - 1)add_edge(which(i, j), which(i, j + 1), s[i][j]),add_edge(which(i, j + 1), which(i, j), t[i][j]);std::cout << sum - maxflow() << std::endl;return 0;
}

（3）[BZOJ1976][BeiJing2010组队]能量魔方 Cube

题意

• 给定一个 $n\times n\times n$ 立方体
• 其中一些格子已经填充了 P 字符或 N 字符
• 要在剩下的格子内填充 P 字符或 N 字符
• 如果相邻（有一个公共面）的格子字符不相同则产生 $1$ 的收益
• 求最大收益
• $n\le 40$

做法

• 还是转化问题
• 理想情况是所有相邻的格子的字符都不相同
• 这时候产生的收益为 $3n\times (n-1)$
• 否则相邻两个同字符的格子有 $1$ 的代价
• 答案就是 $3n\times (n-1)$ 减去最小代价
• 和（1）差不多，但这里已经填充的格子不能再改变
• 所以只需要把 $S$ 到一个格子的边容量由 $1$ 改为 $\infty$ 即可
• 一个格子到 $T$ 的边同理
• 然后对于相邻两个格子 $u$ 和 $v$ ，如果 $u$ 和 $v$ 同字符则产生代价
• 与前两题不同，前两题都是不同时产生代价
• 但这个立方体是个二分图
• 所以对立方体黑白染色之后，这个限制就可以解决了
• 具体地
• 如果 $u$ 的 $x$ 、 $y$ 、 $z$ 坐标之和为奇数且 $u$ 初始已经填充了 N ，或者坐标之和为偶数且初始已经填充了 P ，则连边 $<S,u,\infty >$ $<u,T,0>$
• 如果 $u$ 的 $x$ 、 $y$ 、 $z$ 坐标值和为奇数且 $u$ 初始已经填充了 P ，或者坐标之和为偶数且初始已经填充了 N ，则连边 $<S,u,0>$ $<u,T,\infty >$
• 否则连边 $<S,u,0>$ $<u,T,0>$
• 容量为 $0$ 的边只是为了便于理解而连的，实际上可以不连
• 可以得出，保留边 $<S,u>$ 表示如果 $u$ 的三个坐标值之和为奇数则填充 N ，否则填充 P
• 边 $<u,T>$ 反之
• 对于相邻两个格子 $u$ 和 $v$ ，连边 $<u,v,1>$ ，$<v,u,1>$ 由于 $u$ 的三个坐标值之和与 $v$ 的三个坐标值之和显然有不同的奇偶性，故这可以表示填充相同字符时产生代价

代码

#include 
#include 
#include 
#include 
#include 
#define For(i, a, b) for (i = a; i <= b; i++)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
#define NF(u) for (int &e = cur[u], v = go[e]; e; e = nxt[e], v = go[e])template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}const int E = 45, N = 65535, M = 2097151, INF = 0x3f3f3f3f,
dx[] = {-1, 1, 0, 0, 0, 0}, dy[] = {0, 0, -1, 1, 0, 0},
dz[] = {0, 0, 0, 0, -1, 1};int n, S, T, ecnt = 1, nxt[M], adj[N], go[M], cap[M], len, que[N],
cur[N], lev[N], ans;
char s[E][E][E];void add_edge(int u, int v, int w)
{nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; cap[ecnt] = w;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u; cap[ecnt] = 0;
}int which(int x, int y, int z)
{return 1 + (x - 1) * n * n + (y - 1) * n + z;
}bool bfs()
{int i;For (i, S, T) cur[i] = adj[i], lev[i] = -1;lev[que[len = 1] = S] = 0;For (i, 1, len){int u = que[i];Edge(u) if (cap[e] && lev[v] == -1){lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}int dinic(int u, int flow)
{if (u == T) return flow;int res = 0, delta;NF(u) if (cap[e] && lev[u] < lev[v]){int delta = dinic(v, Min(cap[e], flow - res));if (delta){cap[e] -= delta; cap[e ^ 1] += delta;res += delta; if (res == flow) break;}}if (res != flow) lev[u] = -1;return res;
}int main()
{int i, j, k, h;std::cin >> n;For (i, 1, n) For (j, 1, n)scanf("%s", s[i][j] + 1);S = 1; T = n * n * n + 2;For (i, 1, n) For (j, 1, n) For (k, 1, n){if (i + j + k & 1){if (s[i][j][k] == 'N') add_edge(S, which(i, j, k), INF);if (s[i][j][k] == 'P') add_edge(which(i, j, k), T, INF);}else{if (s[i][j][k] == 'P') add_edge(S, which(i, j, k), INF);if (s[i][j][k] == 'N') add_edge(which(i, j, k), T, INF);}For (h, 0, 5){int x = i + dx[h], y = j + dy[h], z = k + dz[h];if (x < 1 || x > n || y < 1 || y > n || z < 1 || z > n) continue;add_edge(which(i, j, k), which(x, y, z), 1);}}ans = 3 * n * n * (n - 1);while (bfs()) ans -= dinic(S, INF);std::cout << ans << std::endl;return 0;
}

（4）[BZOJ2132]圈地计划

题意

• $n\times m$ 的变量矩阵 x i , j x_{i,j} xi,j​
• x i , j x_{i,j} xi,j​ 取 $0$ 有 a i , j a_{i,j} ai,j​ 的收益
• x i , j x_{i,j} xi,j​ 取 $1$ 有 b i , j b_{i,j} bi,j​ 的收益
• 任意相邻（一条公共边）的 $(i,j)$ $(u,v)$ （注意， $(i,j)(u,v)$ 和 $(u,v)(i,j)$ 会计算两次），如果 $(i,j)$ 和 $(u,v)$ 的取值不同则有 c i , j c_{i,j} ci,j​ 的额外收益
• 求最大收益
• $n,m\le 100$ , a i , j , b i , j , c i , j ≤ 1000 a_{i,j},b_{i,j},c_{i,j}\le1000 ai,j​,bi,j​,ci,j​≤1000

做法

• （2）（3）的思想结合
• 还是转化问题并黑白染色
• 如果 $i+j$ 为奇数，则 < S , ( i , j ) , a i , j > <S,(i,j),a_{i,j}> <S,(i,j),ai,j​> < ( i , j ) , T , b i , j > <(i,j),T,b_{i,j}> <(i,j),T,bi,j​>
• 否则 < S , ( i , j ) , b i , j > <S,(i,j),b_{i,j}> <S,(i,j),bi,j​> < ( i , j ) , T , a i , j > <(i,j),T,a_{i,j}> <(i,j),T,ai,j​>
• 相邻的 $(i,j)$ $(u,v)$ （ $(i,j)(u,v)$ 和 $(u,v)(i,j)$ 需要进行两次）连边 < ( i , j ) , ( u , v ) , c i , j > <(i,j),(u,v),c_{i,j}> <(i,j),(u,v),ci,j​> < ( u , v ) ( i , j ) , c i , j > <(u,v)(i,j),c_{i,j}> <(u,v)(i,j),ci,j​>
• 答案为
• ∑ i , j a i , j + ∑ i , j b i , j + ∑ ∣ i − j ∣ + ∣ u − v ∣ = 1 c i , j − 最 小 割 \sum_{i,j} a_{i,j}+\sum_{i,j} b_{i,j}+\sum_{|i-j|+|u-v|=1}c_{i,j}-最小割 i,j∑​ai,j​+i,j∑​bi,j​+∣i−j∣+∣u−v∣=1∑​ci,j​−最小割

代码

#include 
#include 
#include 
#include 
#include 
#define For(i, a, b) for (i = a; i <= b; i++)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
#define NF(u) for (int &e = cur[u], v = go[e]; e; e = nxt[e], v = go[e])inline int read()
{int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}const int N = 1e4 + 10, M = 2e5 + 5, dx[] = {-1, 1, 0, 0},
dy[] = {0, 0, -1, 1}, INF = 0x3f3f3f3f;int n, m, ecnt = 1, S, T, nxt[M], adj[N], go[M], cap[M], len, que[N],
lev[N], cur[N];int which(int x, int y) {return (x - 1) * m + y + 1;}void add_edge(int u, int v, int w)
{nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; cap[ecnt] = w;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u; cap[ecnt] = 0;
}bool bfs()
{int i;For (i, S, T) cur[i] = adj[i], lev[i] = -1;lev[que[len = 1] = S] = 0;For (i, 1, len){int u = que[i];Edge(u) if (cap[e] && lev[v] == -1){lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}int dinic(int u, int flow)
{if (u == T) return flow;int res = 0, delta;NF(u) if (cap[e] && lev[u] < lev[v]){int delta = dinic(v, Min(cap[e], flow - res));if (delta){cap[e] -= delta; cap[e ^ 1] += delta;if ((res += delta) == flow) break;}}if (res != flow) lev[u] = -1;return res;
}int maxflow()
{int res = 0;while (bfs()) res += dinic(S, INF);return res;
}int main()
{int i, j, k, x, sum = 0;n = read(); m = read();S = 1; T = n * m + 2;For (i, 1, n) For (j, 1, m){sum += (x = read());if (i + j & 1) add_edge(S, which(i, j), x);else add_edge(which(i, j), T, x);}For (i, 1, n) For (j, 1, m){sum += (x = read());if (i + j & 1) add_edge(which(i, j), T, x);else add_edge(S, which(i, j), x);}For (i, 1, n) For (j, 1, m){x = read();For (k, 0, 3){int tx = i + dx[k], ty = j + dy[k];if (tx < 1 || tx > n || ty < 1 || ty > m) continue;add_edge(which(i, j), which(tx, ty), x);add_edge(which(tx, ty), which(i, j), x);sum += x;}}std::cout << sum - maxflow() << std::endl;return 0;
}

（5）[BZOJ3218]a + b Problem

题意

• 给定 $n$ 个格子，要求染成黑白两色
• 第 $i$ 个格子染成黑色有 b i b_i bi​ 的收益
• 第 $i$ 个格子染成白色有 w i w_i wi​ 的收益
• 如果第 $i$ 个格子为黑色且存在一个 $j<i$ 使得 l i ≤ a j ≤ r i l_i\le a_j\le r_i li​≤aj​≤ri​ 且格子 $j$ 为白色则有 p i p_i pi​ 的代价
• 求总收益减去总代价的最大值
• 数据范围见原题

做法

• 还是一样， $S$ 向每个 $i$ 连边，容量为 b i b_i bi​ ，每个 $i$ 向 $T$ 连边，容量为 w i w_i wi​
• 边 $<S,i>$ 保留表示 $i$ 格子为黑，否则为白
• 关键就在于如何限制「存在一个 $j<i$ 」
• 我们能够想到对 $i$ 建虚拟点 i ′ i' i′ ，由 $i$ 向 i ′ i' i′ 连一条容量为 p i p_i pi​ 的边
• 然后由 i ′ i' i′ 向所有 j < i , l i ≤ a j ≤ r i j<i,l_i\le a_j\le r_i j<i,li​≤aj​≤ri​ 的 $j$ 连边，容量 $\infty$ （割不掉）
• 这时候只要有至少一个满足条件的 $j$ 使得边 $<j,T>$ 保留，且边 $<S,i>$ 保留，我们就必须割边 < i , i ′ > <i,i'> <i,i′>
• 这样答案就是 ∑ i = 1 n ( b i + w i ) − 最 小 割 \sum_{i=1}^n(b_i+w_i)-最小割 ∑i=1n​(bi​+wi​)−最小割
• 这样建图边数是 O ( n 2 ) O(n^2) O(n2) 的，在 $5000$ 的规模下时空复杂度都过不去
• 但可以发现这 O ( n 2 ) O(n^2) O(n2) 条边大部分都是 i ′ i' i′ 向 $[1,i-1]$ 内 $a$ 在 [ l i , r i ] [l_i,r_i] [li​,ri​] 内的点连的边
• 使用主席树优化建图
• 维护一棵可持久化线段树，第 $i$ 个历史版本为前 $i$ 个格子的状态，下标为 $a$ 的值
• 父亲向子节点连 $\infty$ 的边
• i ′ i' i′ 向历史版本 $i-1$ 内 $a$ 的值区间为 [ l i , r i ] [l_i,r_i] [li​,ri​] 的所有点连边时，只需要连向 [ l i , r i ] [l_i,r_i] [li​,ri​] 在线段树上拆出的 $O(\log n)$ 个区间
• 点数和边数都是 $O(n\log n)$
• 一个细节：建立主席树时，到达叶子节点后必须将该叶子节点连向上一个版本的对应叶子，否则如果有多个重复的 $a$ 值时只能处理到最近一次出现的位置，在 UOJ 上可以得到 80 分的高分

代码

#include 
#include 
#include 
#include 
#include 
#define For(i, a, b) for (i = a; i <= b; i++)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
#define NF(u) for (int &e = cur[u], v = go[e]; e; e = nxt[e], v = go[e])inline int read()
{int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}typedef long long ll;const int N = 5005, M = 1e6 + 5, INF = 0x3f3f3f3f;int n, a[N], b[N], w[N], l[N], r[N], p[N], rt[N], ecnt = 1, nxt[M],
adj[M], go[M], cap[M], len, que[M], cur[M], lev[M], ToT, to[N], S, T;struct node
{int lc, rc;
} Tr[M];void add_edge(int u, int v, int w)
{nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; cap[ecnt] = w;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u; cap[ecnt] = 0;
}void ins(int y, int &x, int l, int r, int i)
{Tr[x = ++ToT] = Tr[y];if (l == r) return add_edge(x, to[i] = ++ToT, INF),add_edge(x, y, INF);int mid = l + r >> 1;if (a[i] <= mid) ins(Tr[y].lc, Tr[x].lc, l, mid, i);else ins(Tr[y].rc, Tr[x].rc, mid + 1, r, i);if (Tr[x].lc) add_edge(x, Tr[x].lc, INF);if (Tr[x].rc) add_edge(x, Tr[x].rc, INF);
}void linkedge(int x, int l, int r, int s, int e, int u)
{if (!x) return;if (l == s && r == e) return add_edge(u, x, INF);int mid = l + r >> 1;if (e <= mid) linkedge(Tr[x].lc, l, mid, s, e, u);else if (s >= mid + 1) linkedge(Tr[x].rc, mid + 1, r, s, e, u);else linkedge(Tr[x].lc, l, mid, s, mid, u),linkedge(Tr[x].rc, mid + 1, r, mid + 1, e, u);
}bool bfs()
{int i;For (i, 1, ToT) cur[i] = adj[i], lev[i] = -1;lev[que[len = 1] = S] = 0;For (i, 1, len){int u = que[i];Edge(u) if (cap[e] && lev[v] == -1){lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}ll dinic(int u, ll flow)
{if (u == T) return flow;ll res = 0, delta;NF(u) if (cap[e] && lev[u] < lev[v]){delta = dinic(v, Min(1ll * cap[e], flow - res));if (delta){cap[e] -= delta; cap[e ^ 1] += delta;res += delta; if (res == flow) break;}}if (res != flow) lev[u] = -1;return res;
}int main()
{int i;ll ans = 0;n = read();For (i, 1, n) a[i] = read(), b[i] = read(), w[i] = read(),l[i] = read(), r[i] = read(), p[i] = read(),ans += b[i] + w[i];S = 1; T = ToT = 2;For (i, 1, n) ins(rt[i - 1], rt[i], 0, 1e9, i);For (i, 1, n) add_edge(S, to[i], b[i]), add_edge(to[i], T, w[i]);For (i, 1, n) add_edge(to[i], ++ToT, p[i]),linkedge(rt[i - 1], 0, 1e9, l[i], r[i], ToT);while (bfs()) ans -= dinic(S, 1e18);std::cout << ans << std::endl;return 0;
}

（6）[BZOJ3144][Hnoi2013]切糕

题意

• 给定一个 $P\times Q\times R$ 的立方体， $R$ 是高度（层数）
• $P\times Q$ 个变量，形如 x i , j ∈ [ 1 , R ] x_{i,j}\in[1,R] xi,j​∈[1,R]
• 规定相邻 $|i-j|+|u-v|=1$ 的 $(i,j)(u,v)$ 需要满足 ∣ x i , j − x u , v ∣ ≤ d |x_{i,j}-x_{u,v}|\le d ∣xi,j​−xu,v​∣≤d
• 求
• ∑ i = 1 P ∑ j = 1 Q v i , j , x i , j \sum_{i=1}^P\sum_{j=1}^Qv_{i,j,x_{i,j}} i=1∑P​j=1∑Q​vi,j,xi,j​​
• 的最小值
• P , Q , R ≤ 40 , 0 ≤ d ≤ R , v i , j , k ≤ 1000 P,Q,R\le 40,0\le d\le R,v_{i,j,k}\le 1000 P,Q,R≤40,0≤d≤R,vi,j,k​≤1000

做法

• 此题和前面五题的区别：变量的取值不仅仅有两个
• 我们考虑对变量 x i , j x_{i,j} xi,j​ 建立 $R+1$ 个点，从 $(i,j,1)$ 一直到 $(i,j,R+1)$
• $<S,(i,j,1),\infty >$
• < ( i , j , k ) , ( i , j , k + 1 ) , v i , j , k > <(i,j,k),(i,j,k+1),v_{i,j,k}> <(i,j,k),(i,j,k+1),vi,j,k​>
• $<(i,j,R+1),T,\infty >$
• 考虑如何使得 v i , j − v u , v > d v_{i,j}-v_{u,v}>d vi,j​−vu,v​>d 时仍然有 $S$ 到 $T$ 的路径（ v i , j − v u , v < − d v_{i,j}-v_{u,v}<-d vi,j​−vu,v​<−d 实际上就是 v u , v − v i , j > d v_{u,v}-v_{i,j}>d vu,v​−vi,j​>d ）
• 发现我们要做的就是对于每个 $k\in [d+1,R+1]$
• 连边 $<(i,j,k),(u,v,k-d),\infty >$
• 讨论一波即可得到正确性
• 答案即为最小割

代码-

#include 
#include 
#include 
#include 
#include 
using namespace std;
inline int read() {int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}
const int W = 45, N = 3e5 + 5, INF = 0x3f3f3f3f;
int P, Q, R, D, S, T, val[W][W][W], ecnt = 1, nxt[N], adj[N], go[N], cap[N],
lev[N], len, que[N], dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};
void add_edge(int u, int v, int w) {nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; cap[ecnt] = w;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u; cap[ecnt] = 0;
}
bool bfs() {int i; memset(lev, -1, sizeof(lev));lev[que[len = 1] = S] = 0;for (i = 1; i <= len; i++) {int u = que[i];for (int e = adj[u], v; e; e = nxt[e])if (cap[e] > 0 && lev[v = go[e]] == -1) {lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}
int dinic(int u, int flow) {if (u == T) return flow;int res = 0, delta;for (int e = adj[u], v; e; e = nxt[e])if (cap[e] > 0 && lev[u] < lev[v = go[e]]) {delta = dinic(v, min(cap[e], flow - res));if (delta) {cap[e] -= delta; cap[e ^ 1] += delta;res += delta; if (res == flow) break;}}if (res != flow) lev[u] = -1;return res;
}
int solve() {int ans = 0;while (bfs()) ans += dinic(S, INF);return ans;
}
int main() {int i, j, k, h; P = read(); Q = read();R = read(); D = read(); S = 1; T = P * Q * (R + 1) + 2;for (k = 1; k <= R; k++) for (i = 1; i <= P; i++)for (j = 1; j <= Q; j++) val[i][j][k] = read();for (i = 1; i <= P; i++) for (j = 1; j <= Q; j++) {int x = (i - 1) * Q + j + 1;add_edge(S, x, INF); for (k = 1; k <= R; k++)add_edge(P * Q * (k - 1) + x, P * Q * k + x, val[i][j][k]);add_edge(P * Q * R + x, T, INF);}for (i = 1; i <= P; i++) for (j = 1; j <= Q; j++)for (h = 0; h < 4; h++) {int x = i + dx[h], y = j + dy[h];if (x < 1 || x > P || y < 1 || y > Q) continue;for (k = D + 1; k <= R + 1; k++)add_edge(P * Q * (k - 1) + (i - 1) * Q + j + 1,P * Q * (k - D - 1) + (x - 1) * Q + y + 1, INF);}printf("%d\n", solve());return 0;
}

（7）[BZOJ1497][NOI2006]最大获利

题意

• 给定一个边和点都带权的无向图，求一个子图
• 使得边权和减去点权的结果最大
• 点数 $\le 5000$
• 边数 $\le 50000$
• 权值 $\le 100$

做法

• 从这题开始，我们引入最小割，也是互斥选择的一个经典模型：最大权闭合子图
• 定义：在一个有向图中选出一个点集 $S$ ，满足不存在边 $<u,v>$ 使得 $u\in S,v\notin S$ ，求选出的所有点的权值和的最大值，这些点的权值可正可负
• 先说建图：源点向所有正权点连容量为该点权值的边，所有负权点向汇点连容量为该点权值相反数的边，对于原图中每条边 $<u,v>$ ，连边 $<u,v,\infty >$
• 最大权闭合子图的点权和就是所有正权点的权值和减去最小割
• 证明：保留边 $<S,u>$ 表示选点 $u$ ，保留边 $<v,T>$ 表示不选点 $v$
• 由于最优性，我们只需要对满足 $u$ 为正权， $v$ 为负权且 $u$ 能到达 $v$ 的点 $u,v$ 进行讨论
• 显然这时候选 $u$ 而不选 $v$ 是不行的
• 这个限制条件也在建图上表现了出来：选 $u$ 而不选 $v$ 表示边 $<S,u>$ 和 $<v,T>$ 都保留，这时候 $S$ 还是能到达 $T$
• 证毕
• 最大权闭合子图可以解决许多含有「选了 $u$ 则必须选 $v$ 」的最优化问题
• 此外，如果要输出点集，则最大权闭合子图为残余网络上从 $S$ 出发能到达的所有点构成的点集（最小割分出的 $S$ 所在的集合）
• 在此题中，可以建立模型：选了边 $(u,v)$ 就必须选点 $u$ 和 $v$
• 于是把边抽象成点，边 $(u,v)$ 对应的点分别向点 $u$ 和 $v$ 连边
• 答案为最大权闭合子图

代码

#include 
#include 
#include 
#include 
#include 
#define For(i, a, b) for (i = a; i <= b; i++)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
#define NF(u) for (int &e = cur[u], v = go[e]; e; e = nxt[e], v = go[e])inline int read()
{int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}typedef long long ll;const int N = 1e5 + 5, M = 1e6 + 5;
const ll INF = 1e18;int n, m, ecnt = 1, nxt[M], adj[N], go[M], S, T, len, que[N],
lev[N], cur[N];
ll cap[M];void add_edge(int u, int v, ll w)
{nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; cap[ecnt] = w;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u; cap[ecnt] = 0;
}bool bfs()
{int i;For (i, S, T) cur[i] = adj[i], lev[i] = -1;lev[que[len = 1] = S] = 0;For (i, 1, len){int u = que[i];Edge(u) if (cap[e] && lev[v] == -1){lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}ll dinic(int u, ll flow)
{if (u == T) return flow;ll res = 0, delta;NF(u) if (cap[e] && lev[u] < lev[v]){delta = dinic(v, Min(cap[e], flow - res));if (delta){cap[e] -= delta; cap[e ^ 1] += delta;res += delta; if (res == flow) break;}}if (res != flow) lev[u] = -1;return res;
}int main()
{int i, x, y, z;ll ans = 0;n = read(); m = read();S = 1; T = n + m + 2;For (i, 1, n) x = read(), add_edge(1 + m + i, T, x);For (i, 1, m) x = read(), y = read(), z = read(),add_edge(S, 1 + i, z), add_edge(1 + i, 1 + m + x, INF),add_edge(1 + i, 1 + m + y, INF), ans += z;while (bfs()) ans -= dinic(S, INF);std::cout << ans << std::endl;return 0;
}

（8）[BZOJ3996][TJOI2015]线性代数

题意

• 给出一个 $n\times n$ 的矩阵 $B$ 和一个 $1\times n$ 的矩阵 $C$
• 求出一个 $1\times n$ 的 $01$ 矩阵 $A$
• 使得 D = ( A × B − C ) × A T D=(A\times B-C)\times A^T D=(A×B−C)×AT 最大
• 其中 A T A^T AT 为 $A$ 的转置
• 输出 $D$
• $1\le n\le 500$ ， $0\le 矩阵元素\le 1000$

做法

• 发现问题等价于选 $i$ 有 C 1 , i C_{1,i} C1,i​ 的代价，同时选 $i$ 和 $j$ 有 B i , j B_{i,j} Bi,j​ 的收益
• 求总收益减去总代价的最大值
• 很容易建立出「选了 B i , j B_{i,j} Bi,j​ 则必须选 − C 1 , i -C_{1,i} −C1,i​ 和 − C 1 , j -C_{1,j} −C1,j​ 」的模型
• 转成最大权闭合子图模型，上最小割直接艹掉

代码

#include 
#include 
#include 
#include 
#include 
#define For(i, a, b) for (i = a; i <= b; i++)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
#define NF(u) for (int &e = cur[u], v = go[e]; e; e = nxt[e], v = go[e])
using namespace std;
inline int read() {int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}
const int N = 505, M = 1e6 + 5, INF = 0x3f3f3f3f;
int n, b[N][N], c[N], ecnt = 1, nxt[M], adj[M], go[M], cap[M],
lev[M], cur[M], len, que[M], S, T, sum;
void add_edge(int u, int v, int w) {nxt[++ecnt] = adj[u]; adj[u] = ecnt;go[ecnt] = v; cap[ecnt] = w;nxt[++ecnt] = adj[v]; adj[v] = ecnt;go[ecnt] = u; cap[ecnt] = 0;
}
bool bfs() {int i;For (i, S, T) lev[i] = -1, cur[i] = adj[i];lev[que[len = 1] = S] = 0;For (i, 1, len) {int u = que[i];Edge(u)if (cap[e] && lev[v] == -1) {lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}
int dinic(int u, int flow) {if (u == T) return flow;int res = 0, delta;NF(u) if (cap[e] && lev[u] < lev[v]) {delta = dinic(v, min(cap[e], flow - res));if (delta) {cap[e] -= delta; cap[e ^ 1] += delta;res += delta; if (res == flow) break;}}if (res != flow) lev[u] = -1;return res;
}
int solve() {int res = 0;while (bfs()) res += dinic(S, INF);return res;
}
int main() {int i, j, tot = 1;n = read();For (i, 1, n) For (j, 1, n) sum += (b[i][j] = read());For (i, 1, n) c[i] = read();S = 1; T = (n * (n + 1) >> 1) + n + 2;For (i, 1, n) For (j, i, n) {tot++;add_edge(S, tot, i == j ? b[i][j] : b[i][j] + b[j][i]);add_edge(tot, 1 + (n * (n + 1) >> 1) + i, INF);if (i != j) add_edge(tot, 1 + (n * (n + 1) >> 1) + j, INF);}For (i, 1, n) add_edge(1 + (n * (n + 1) >> 1) + i, T, c[i]);cout << sum - solve() << endl;return 0;
}

（9）[BZOJ4873][Shoi2017]寿司餐厅

题意

• 较长，见原题

做法

• 从「每个 d i , j d_{i,j} di,j​ 只能选一次」开始讨论
• 考虑选出的 $d$ 来自的位置集合需要满足的条件
• 抽象到二维平面上长这样（选出的 $d$ 位置集合即为蓝色部分）
  
• 简单地说，对于 $i<j$ ，如果选了 d i , j d_{i,j} di,j​ 就必须选 d i + 1 , j d_{i+1,j} di+1,j​ 和 d i , j − 1 d_{i,j-1} di,j−1​
• 再考虑花费的钱数 m x 2 + c x mx^2+cx mx2+cx ，对于 $cx$ 只需要对于每个 $i$ 将 d i , i d_{i,i} di,i​ 减去 a i a_i ai​ 即可
• 而对于 m x 2 mx^2 mx2 则需要对于每种代号新建一个点，点权为代号的二次方乘上 $m$ 的相反数，对于每个 $1\le i\le n$ 由 d i , i d_{i,i} di,i​ 向代号 a i a_i ai​ 连边
• 仍然是最大权闭合子图，最小割解决

代码

#include 
#include 
#include 
#include 
#include inline int read()
{int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}typedef long long ll;const int E = 105, N = 1e4 + 5, M = 4e5 + 5, INF = 0x3f3f3f3f;int n, m, a[E], d[E][E], S, T, tot = 1, id[E][E], ecnt = 1, nxt[M],
adj[N], go[M], cap[M], len, que[N], cur[N], lev[N];
ll ans;void add_edge(int u, int v, int w)
{nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v; cap[ecnt] = w;nxt[++ecnt] = adj[v]; adj[v] = ecnt; go[ecnt] = u; cap[ecnt] = 0;
}bool bfs()
{for (int i = S; i <= T; i++)cur[i] = adj[i], lev[i] = -1;lev[que[len = 1] = S] = 0;for (int i = 1; i <= len; i++){int u = que[i];for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])if (cap[e] && lev[v] == -1){lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}ll dinic(int u, ll flow)
{if (u == T) return flow;ll res = 0, delta;for (int &e = cur[u], v = go[e]; e; e = nxt[e], v = go[e])if (cap[e] && lev[u] < lev[v]){delta = dinic(v, Min(1ll * cap[e], flow - res));if (delta){cap[e] -= delta; cap[e ^ 1] += delta;res += delta; if (res == flow) break;}}if (res < flow) lev[u] = -1;return res;
}int main()
{n = read(); m = read();for (int i = 1; i <= n; i++) a[i] = read();S = 1; T = 1002 + (n * (n + 1) >> 1);for (int i = 1; i <= n; i++)for (int j = i; j <= n; j++)d[i][j] = read(), id[i][j] = ++tot;for (int i = 1; i <= n; i++) d[i][i] -= a[i];for (int i = 1; i <= n; i++)for (int j = i; j <= n; j++)if (d[i][j] > 0) add_edge(S, id[i][j], d[i][j]), ans += d[i][j];else if (d[i][j] < 0) add_edge(id[i][j], T, -d[i][j]);for (int i = 1; i <= 1000; i++)add_edge(1 + (n * (n + 1) >> 1) + i, T, m * i * i);for (int i = 1; i <= n; i++)for (int j = i + 1; j <= n; j++){add_edge(id[i][j], id[i + 1][j], INF);add_edge(id[i][j], id[i][j - 1], INF);}for (int i = 1; i <= n; i++)add_edge(id[i][i], 1 + (n * (n + 1) >> 1) + a[i], INF);while (bfs()) ans -= dinic(S, 1e18);std::cout << ans << std::endl;return 0;
}

（10）[BZOJ4501]旅行

题意

• 给定一个 $n$ 点 $m$ 边的 DAG
• 从 $1$ 开始，每次等概率随机地选一条出边走过去，如果没有出边则结束旅行
• 删掉一些边，有 $k$ 个约束形如 $(a,b)$ ，表示第 $b$ 条边被删掉则第 $a$ 条边也必须删掉，其中第 $a$ 条边和第 $b$ 条边有共同起点
• 求删边后从 $1$ 出发走过的路径长度的期望的最大值
• $1\le n\le 50$ , $0\le m\le 500$ ， $0\le k\le 2000$ ，图可能有重边

做法

• 这是一道综合性较强的非常不错的题，所以放在了最后讲
• 我们知道，对于 DAG ，如果 $f[u]$ 表示从 $u$ 走到终态的期望步数，那么
• f [ u ] = 1 + ∑ < u , v > f [ v ] d u f[u]=1+\frac {\sum_{<u,v>}f[v]}{d_u} f[u]=1+du​∑<u,v>​f[v]​
• 按照拓扑序逆序 DP
• 其中 d u d_u du​ 为点 $u$ 的度数
• 而如果 $f[u]$ 表示合法删边后从 $u$ 走到终态的期望步数最大值，
• 则我们要求的就是 $u$ 的出边的一个子集，使得这个子集满足某些限制（ $a$ 在子集内则 $b$ 必须在子集内），使得选出的所有边的终点的 $f$ 值的平均值最大，这个最大值加上 $1$ 就是 $f[u]$
• 我们现在想解决的问题转化成「最大平均权闭合子图」
• 看到最优化目标是分数，我们很容易想到分数规划
• 二分答案 $mid$ 后，将权值全部减去 $mid$ 之后求最大权闭合子图，判断其是否大于 $0$ ，如果大于 $0$ 则平均值大于 $mid$ ，反之亦然
• 注意终态的 $f$ 为 $0$
• 最后答案 $f[1]$

代码

#include 
#include 
#include 
#include 
#include 
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
#define Edge2(u) for (int e = adj2[u]; e; e = nxt2[e])
#define Edge3(u) for (int e = adj3[u], v = go3[e]; e; e = nxt3[e], v = go3[e])
#define Edge4(u) for (int e = adj4[u], v = go4[e]; e; e = nxt4[e], v = go4[e])
#define NF(u) for (int &e = cur[u], v = go4[e]; e; e = nxt4[e], v = go4[e])inline int read()
{int res = 0; bool bo = 0; char c;while (((c = getchar()) < '0' || c > '9') && c != '-');if (c == '-') bo = 1; else res = c - 48;while ((c = getchar()) >= '0' && c <= '9')res = (res << 3) + (res << 1) + (c - 48);return bo ? ~res + 1 : res;
}template <class T>
inline T Min(const T &a, const T &b) {return a < b ? a : b;}const int N = 60, M = 4005, L = 1e5 + 5;
const double INF = 1e20;int n, m, k, ecnt, nxt[M], adj[N], st[M], go[M], ecnt2, nxt2[M],
adj2[N], w1[M], w2[M], He, Ta, Q[N], d[N], ecnt3, nxt3[M], adj3[N],
go3[M], S, T, tot, _u[M], ecnt4, nxt4[L], adj4[M], go4[L], len, que[M],
cur[M], lev[M], to[M];
double f[N], cap4[L];void add_edge(int u, int v)
{nxt[++ecnt] = adj[u]; adj[u] = ecnt; st[ecnt] = u; go[ecnt] = v;d[u]++;
}void add_edge2(int u, int v, int w)
{nxt2[++ecnt2] = adj2[u]; adj2[u] = ecnt2; w1[ecnt2] = v; w2[ecnt2] = w;
}void add_edge3(int u, int v)
{nxt3[++ecnt3] = adj3[u]; adj3[u] = ecnt3; go3[ecnt3] = v;
}void add_edge4(int u, int v, double w)
{nxt4[++ecnt4] = adj4[u]; adj4[u] = ecnt4; go4[ecnt4] = v; cap4[ecnt4] = w;nxt4[++ecnt4] = adj4[v]; adj4[v] = ecnt4; go4[ecnt4] = u; cap4[ecnt4] = 0;
}bool bfs()
{int i;For (i, 1, tot + 2) cur[i] = adj4[i], lev[i] = -1;lev[que[len = 1] = S] = 0;For (i, 1, len){int u = que[i];Edge4(u) if (cap4[e] > 1e-8 && lev[v] == -1){lev[que[++len] = v] = lev[u] + 1;if (v == T) return 1;}}return 0;
}double dinic(int u, double flow)
{if (u == T) return flow;double res = 0, delta;NF(u) if (cap4[e] > 1e-8 && lev[u] < lev[v]){delta = dinic(v, Min(cap4[e], flow - res));if (delta > 1e-8){cap4[e] -= delta; cap4[e ^ 1] += delta;res += delta; if (fabs(res - flow) <= 1e-8) break;}}if (fabs(res - flow) > 1e-8) lev[u] = -1;return res;
}double maxflow()
{double res = 0;while (bfs()) res += dinic(S, INF);return res;
}bool check(int uc, double mid)
{int i;S = tot + 1; T = tot + 2; ecnt4 = 1;For (i, 1, tot + 2) adj4[i] = 0;double res = 0;For (i, 1, tot){int u = go[_u[i]]; to[_u[i]] = i;if (f[u] - mid > 0) add_edge4(S, i, f[u] - mid),res += f[u] - mid;else add_edge4(i, T, mid - f[u]);}Edge2(uc) add_edge4(to[w1[e]], to[w2[e]], INF);return res - maxflow();
}int main()
{int i, x, y;n = read(); m = read(); k = read();while (m--) x = read(), y = read(), add_edge(x, y), add_edge3(y, x);while (k--) x = read(), y = read(), add_edge2(st[x], x, y);For (i, 1, n) if (!d[i]) Q[++Ta] = i;while (He < Ta){int u = Q[++He];tot = 0;Edge3(u) if (!(--d[v])) Q[++Ta] = v;Edge(u) _u[++tot] = e;if (!tot) continue;double l = 0, r = n;while (r - l > 1e-10){double mid = (l + r) / 2;if (check(u, mid)) l = mid;else r = mid;}f[u] = r + 1;}printf("%.10lf\n", f[1]);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！