题目
思路&做法
明显的最小割（其实是之前做过一道类似的题）
-
S向每一个格子连容量为(b_i)的边
-
每一个格子向T连容量为(w_i)的边
-
对于格子(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)的边。
代码
#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
", 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
*/