【BZOJ3218】【UOJ#77】a + b Problem

## 题目 ## [题目在这里](http://uoj.ac/problem/77) ## 思路&做法 ## 明显的最小割（其实是之前做过一道类似的题） 1. S向每一个格子连容量为$b_i$的边 2. 每一个格子向T连容量为$w_i$的边 3. 对于格子$i$向满足条件的格子$j(1 \leq j < i, l_i \leq a_j \leq r_i)$连容量为$p_i$的边 但是考虑到这题恶心的数据范围， 这样做很明显会TLE。 算法的瓶颈在第三步。我们发现$j$的范围看起来像是一个像二维偏序的东西， 于是便可以用主席树来优化一下， 对于每个节点$i$新建一个节点$k$，由i向k连容量为$p_i$的边， 由$k$向主席树中$j$的范围的对应的节点连容量为$inf$的边。 ## 代码 ## ```cpp #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include <cmath> #include <queue> #include <vector> #include <algorithm> using namespace std; const int INF = 0x7F7F7F7F; const int N = 50010, M = 1450010; struct edge { int from, to, flow, cap; edge() { } edge(int _1, int _2, int _3, int _4) : from(_1), to(_2), flow(_3), cap(_4) { } }; struct Dinic { edge edges[M]; int head[165022], nxt[M], tot; int L, R; inline void init() { memset(head, -1, sizeof(head)); tot = 0; } void add_edge(int x, int y, int z) { edges[tot] = edge(x, y, 0, z); nxt[tot] = head[x]; head[x] = tot++; edges[tot] = edge(y, x, 0, 0); nxt[tot] = head[y]; head[y] = tot++; } int s, t; int d[165022]; bool bfs() { memset(d, -1, sizeof(d)); queue<int> q; d[s] = 0; q.push(s); while (!q.empty()) { int x = q.front(); q.pop(); for (int i = head[x]; ~i; i = nxt[i]) { edge & e = edges[i]; if (e.cap > e.flow && d[e.to] == -1) { d[e.to] = d[x] + 1; q.push(e.to); } } } return d[t] != -1; } int cur[165022]; int dfs(int x, int a) { if (x == t || a == 0) return a; int flow = 0, f; for (int & i = cur[x]; ~i; i = nxt[i]) { edge & e = edges[i]; if (d[e.to] == d[x] + 1 && (f = dfs(e.to, min(a, e.cap-e.flow))) > 0) { e.flow += f; edges[i^1].flow -= f; a -= f; flow += f; if (a == 0) break; } } return flow; } int maxflow(int _s, int _t) { s = _s, t = _t; int flow = 0; while (bfs()) { for (int i = L; i <= R; i++) cur[i] = head[i]; flow += dfs(s, INF); } return flow; } } dinic; int n; int root[N]; struct SegmentTree { int ls[N*20], rs[N*20], sz; void update(int & cur, int pre, int l, int r, int p, int node) { cur = ++sz; if (l == r) { if (pre) dinic.add_edge(cur, pre, INF); dinic.add_edge(cur, node, INF); return; } ls[cur] = ls[pre]; rs[cur] = rs[pre]; int mid = (l + r) >> 1; if (p <= mid) update(ls[cur], ls[pre], l, mid, p, node); else update(rs[cur], rs[pre], mid+1, r, p, node); dinic.add_edge(cur, ls[cur], INF); dinic.add_edge(cur, rs[cur], INF); } void link(int cur, int l, int r, int ql, int qr, int node) { if (ql == l && qr == r) dinic.add_edge(node, cur, INF); else { int mid = (l + r) >> 1; if (qr <= mid) link(ls[cur], l, mid, ql, qr, node); else if (ql > mid) link(rs[cur], mid+1, r, ql, qr, node); else link(ls[cur], l, mid, ql, mid, node), link(rs[cur], mid+1, r, mid+1, qr, node); } } } st; int a[N], w[N], b[N], L[N], R[N], p[N]; int num[N], total; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d %d %d %d %d %d", &a[i], &b[i], &w[i], &L[i], &R[i], &p[i]); num[++total] = a[i]; num[++total] = L[i]; num[++total] = R[i]; } sort(num+1, num+total+1); total = unique(num+1, num+total+1) - num - 1; for (int i = 1; i <= n; i++) { a[i] = lower_bound(num+1, num+1+total, a[i]) - num; L[i] = lower_bound(num+1, num+1+total, L[i]) - num; R[i] = lower_bound(num+1, num+1+total, R[i]) - num; } int ans = 0; dinic.init(); int S = n + n + 1, T = n + n + 2; st.sz = n + n + 2; for (int i = 1; i <= n; i++) { dinic.add_edge(S, i, b[i]); dinic.add_edge(i, T, w[i]); dinic.add_edge(i, i+n, p[i]); if (i > 1) st.link(root[i-1], 1, total, L[i], R[i], i+n); st.update(root[i], root[i-1], 1, total, a[i], i); ans += b[i] + w[i]; } dinic.L = 0, dinic.R = st.sz; ans -= dinic.maxflow(S, T); printf("%d\n", ans); } /* 10 0 1 7 3 9 2 7 4 0 9 10 5 1 0 4 2 10 2 7 9 1 5 7 2 6 3 5 3 6 2 6 6 4 1 8 1 6 1 6 0 6 5 2 2 5 0 9 3 5 1 3 0 2 5 5 6 7 1 1 2 ``` */