zqs`s blog

有朋自远方来，虽远必诛

题解 【P5331 [SNOI2019]通信】

发表于 更新于 分类于 Valine：

我tm，调了一整天终于A了/px/px/px

好久没写主席树手生了啊/kk

费用流。建立超级源 $s$ 以及超级汇 $t$。对于每个哨站建立两个点 $i$ 和 $i^{\prime}$，从 $s$ 向 $i$ 连一条容量为 $1$，费用为 $0$ 的边，表示一个哨站只用连一次。从 $i$ 向 $t$ 连一条容量为 $1$，费用为 $w$ 的边，代表直接连到控制中心。从 $i^{\prime}$ 向 $t$ 连一条容量为 $1$，费用为 $0$ 的边，代表每个哨站只能被后面的至多一个哨站连接。从 $i$ 向 $j^{\prime}(j<i)$连一条容量为 $1$，费用为 $\lvert a_i-a_j\rvert$，代表连向之前的点。

$1000$ 个点 $10^6$ 条边，凭着信仰交了一发，发现只有90pts（

？暴力90pts考试谁还会想正解啊

瓶颈在于每个点向之前的点连边。相当于 $i$ 向 $[1,i-1]$ 连边，且流量固定，费用为一个绝对值的式子。

看到绝对值按照套路拆开，建立权值线段树然后线段树优化建图？

嗯好像很可做的样子。

但是 $a_i$ 达到了 $10^9$，$\log 10^9$有 $30$，而分类讨论绝对值有个 $2$ 的常数，乘一下 $60$，暴力连边倒还有个除以二的常数。。。这和暴力差不多了啊。。。

所以先离散化一下 $a$ 数组是必须的。$2\times \log 300\approx 18$，这下就可以把暴力的 $150$ 吊起来打了。

那么讲一下如何线段树优化建图。

由于我们建的是权值线段树，所以 $i$ 可以拆分为两个边权分别为 $a_i-a_j$ 与 $a_j-a_i$ 的区间 $[1,a_i],[a_i+1,\infty]$。对于两种情况分别建一棵权值线段树。从表示去区间 $[i,i]$ 的叶子节点向 $a_j=i$ 的点 $j^{\prime}$ 连一条容量为 INF，费用为 $0$ 的边。

点 $i$ 分别向两个区间连边，对于到线段树上一点的连边，边权为 $\pm a_i$ 。

但是 $i$ 只能向之前的点连边，所以我们把线段树换成主席树搞一搞就好了。

好久没写主席树了，写完了各种锅，自闭了。

点击显示/隐藏代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define int long long

const int INF = 1e15;
inline int abs(const int k) {return k >= 0 ? k : -k;}
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt, cap, cost;
} e[2000005];
struct Node {
	int v, id;
	inline bool operator < (const Node a) const {return v < a.v;}
} b[1005];
int head[50005], dis[50005], cur[50005], a[1005], tot = 1, tot2, n, s, t;
int ls[50005], rs[50005], root1[50005], root2[50005], val[1005];
bool vis[50005], mark[50005];
std::queue<int> Q;
inline void AddEdge(const int u, const int v, const int cap, const int cost) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
	e[tot].cap = cap, e[tot].cost = cost;
	e[++ tot].to = u, e[tot].nxt = head[v], head[v] = tot;
	e[tot].cap = 0, e[tot].cost = -cost;
}

void Link(int O, int L, int R, int l, int r, int p, int type) {
	if (L <= l && r <= R) {
		if (type == 1) AddEdge(p, O, 1, val[p]);
		else AddEdge(p, O, 1, -val[p]);
		return;
	}
	int mid = l + r >> 1;
	if (L <= mid && ls[O]) Link(ls[O], L, R, l, mid, p, type);
	if (mid < R && rs[O]) Link(rs[O], L, R, mid + 1, r, p, type);
}
void update(int O, int l, int r, int p, const int type, const int root) {
	if (l == r) {
		if (type == 1) AddEdge(O, p + n, INF, -val[p]);
		else AddEdge(O, p + n, INF, val[p]);
		return;
	}
	int mid = l + r >> 1;
	if (a[p] <= mid) {
		if (rs[root]) AddEdge(O, rs[O] = rs[root], INF, 0);
		AddEdge(O, ls[O] = ++ tot2, INF, 0);
		update(ls[O], l, mid, p, type, ls[root]);
	}
	else {
		if (ls[root]) AddEdge(O, ls[O] = ls[root], INF, 0);
		AddEdge(O, rs[O] = ++ tot2, INF, 0);
		update(rs[O], mid + 1, r, p, type, rs[root]);
	}
}

bool spfa() {
	memcpy(cur, head, sizeof cur);
	memset(dis, 0x3f, sizeof dis);
	memset(vis, 0, sizeof vis);
	dis[s] = 0;
	Q.push(s);
	while (Q.size()) {
		int u = Q.front();
		Q.pop();
		mark[u] = false;
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if (e[i].cap && dis[u] + e[i].cost < dis[v]) {
				dis[v] = dis[u] + e[i].cost;
				if (!mark[v]) Q.push(v), mark[v] = true;
			}
		}
	}
	return dis[t] < INF;
}

int dfs(const int u, const int flow) {
	if (u == t) return flow;
	vis[u] = true;
	int used = 0, tmp = 0;
	for (int i = cur[u]; i; i = e[i].nxt) {
		if (!vis[e[i].to] && dis[u] + e[i].cost == dis[e[i].to] && e[i].cap) {
			tmp = dfs(e[i].to, min(e[i].cap, flow - used));
			used += tmp, e[i].cap -= tmp, e[i ^ 1].cap += tmp;
			if (used == flow) return used;
		}
	}
	return used;
}

int Dinic() {
	int Maxflow = 0, Mincost = 0, flow = 0;
	while (spfa()) Maxflow += (flow = dfs(s, INF)), Mincost += dis[t] * flow;
	return Mincost;
}

signed main() {
	int w, len = 0;
	scanf("%lld%lld", &n, &w);
	s = 0, t = 2 * n + 1;
	for (int i = 1; i <= n; ++ i) {
		scanf("%lld", &b[i].v), b[i].id = i;
		AddEdge(s, i, 1, 0), AddEdge(i, t, 1, w);
		AddEdge(i + n, t, 1, 0);
	}
	std::sort(b + 1, b + n + 1);
	b[0].v = -1;
	for (int i = 1; i <= n; ++ i) {
		if (b[i].v != b[i - 1].v) ++ len;
		a[b[i].id] = len, val[b[i].id] = b[i].v;
	}
	root1[0] = 2 * n + 2, root2[0] = tot2 = 2 * n + 3;
	for (int i = 1; i <= n; ++ i) {
		root1[i] = ++ tot2, root2[i] = ++ tot2;
		Link(root1[i - 1], 1, a[i], 1, len, i, 1);
		if (a[i] != len) Link(root2[i - 1], a[i] + 1, len, 1, len, i, 2);
		update(root1[i], 1, len, i, 1, root1[i - 1]);
		update(root2[i], 1, len, i, 2, root2[i - 1]);
	}
	printf("%lld", Dinic());
	return 0;
}
-------------本文结束感谢您的阅读-------------