题解 P5029 【T'ill It's Over】
GKxx
2019-05-18 22:50:27
线段树优化连边+网络流模板题。
考虑一张$k$个结点的图。操作1直接连边，操作2、3就枚举区间的每个点连边，操作4就分别枚举两个区间的点连边，以上边的容量都设为相应的$l$。然后源点向$1$连边，$k$向汇点连边，容量都为$n$，跑最大流即可。
这个复杂度肯定不行，显然可以用线段树优化连边。
开两棵线段树$T_1,T_2$，$T_1$体现外部结点连入区间，$T_2$体现区间连出到外部结点。$T_1$内部从上往下连边，$T_2$内部从下往上连边。注意两棵树的叶子节点应该共用。
我们可以将这4种连边都统一为区间$[l_1,r_1]$向区间$[l_2,r_2]$连边，单个点也可以看做左右端点相等的区间。我们新建两个点$u,v$，从$u$向$v$连边容量为$l$，然后在$T_2$上从区间$[l_1,r_1]$向$u$连边，在$T_1$上从$v$向区间$[l_2,r_2]$连边，这些边容量都是$\infty$。
然后跑最大流即可。
最近做了好几道这种线段树优化建图的题了，比如十二省联考2019字符串问题，SNOI2019通信
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
const int maxv = 1e6 + 7, maxe = 2e6 + 7, inf = INT_MAX;
struct Network {
int v[maxe << 1], cap[maxe << 1], flow[maxe << 1], next[maxe << 1], tot;
int head[maxv], curr[maxv], height[maxv];
int s, t, V;
Network() : tot(-1) {}
void addedge(int x, int y, int c) {
v[++tot] = y; cap[tot] = c; next[tot] = head[x]; head[x] = tot;
v[++tot] = x; cap[tot] = 0; next[tot] = head[y]; head[y] = tot;
}
bool bfs() {
static int q[maxv] = {0};
int l = 0, r = 1;
for (int i = 1; i <= V; ++i) height[i] = 0;
height[q[1] = s] = 1;
while (l < r) {
int x = q[++l];
for (int i = head[x]; ~i; i = next[i])
if (cap[i] > flow[i] && !height[v[i]])
height[q[++r] = v[i]] = height[x] + 1;
}
return height[t];
}
int dfs(int x, int cf) {
if (x == t || !cf) return cf;
int getf = 0;
for (int i = curr[x]; ~i; i = next[i], curr[x] = i)
if (cap[i] > flow[i] && height[v[i]] == height[x] + 1) {
int nf = dfs(v[i], std::min(cap[i] - flow[i], cf));
if (nf) {
flow[i] += nf; flow[i ^ 1] -= nf; getf += nf;
if (!(cf -= nf)) break;
}
}
return getf;
}
int maxflow() {
int ans = 0;
while (bfs()) {
for (int i = 1; i <= V; ++i) curr[i] = head[i];
ans += dfs(s, inf);
}
return ans;
}
};
Network G;
struct Node {
int lc, rc;
Node() : lc(0), rc(0) {}
};
Node T[maxv];
int tot, root1, root2;
int n, m, K, s, t;
inline int newNode() { G.head[++tot] = -1; return tot; }
void build(int &o1, int &o2, int l, int r) {
o1 = newNode();
o2 = l == r ? o1 : newNode();
if (l == r) {
if (l == 1) G.addedge(s, o1, n);
if (l == K) G.addedge(o1, t, n);
return;
}
int mid = (l + r) >> 1;
build(T[o1].lc, T[o2].lc, l, mid);
build(T[o1].rc, T[o2].rc, mid + 1, r);
G.addedge(o1, T[o1].lc, inf);
G.addedge(o1, T[o1].rc, inf);
G.addedge(T[o2].lc, o2, inf);
G.addedge(T[o2].rc, o2, inf);
}
void link(int o, int lb, int rb, int l, int r, int u, int d) {
if (!o || l > rb || r < lb) return;
if (l <= lb && r >= rb) {
if (d == 1) G.addedge(u, o, inf);
else G.addedge(o, u, inf);
return;
}
int mid = (lb + rb) >> 1;
link(T[o].lc, lb, mid, l, r, u, d);
link(T[o].rc, mid + 1, rb, l, r, u, d);
}
int main() {
read(n, m, K);
s = newNode(); t = newNode();
G.s = s; G.t = t;
build(root1, root2, 1, K);
for (int i = 1; i <= m; ++i) {
int op, lim; read(op, lim);
int from = newNode(), to = newNode();
G.addedge(from, to, lim);
int l1, r1, l2, r2;
if (op == 1) {
read(l1, l2);
r1 = l1; r2 = l2;
} else if (op == 2) {
read(l1, r1, l2);
r2 = l2;
} else if (op == 3) {
read(l1, l2, r2);
r1 = l1;
} else read(l1, r1, l2, r2);
link(root1, 1, K, l2, r2, to, 1);
link(root2, 1, K, l1, r1, from, 2);
}
G.V = tot;
writeln(G.maxflow());
return 0;
}
```