zqs`s blog

有朋自远方来，虽远必诛

5-16图论专练总结

发表于 更新于 分类于 Valine：

果然练了两个多月图论还是那么菜啊。

$A$

给你一个 $n$ 节点 $m$ 条边的无向图，无向图中可能存在“环”(回路)。

编号到的这个点，被称为关键点。何老板要你删掉一些边，使得所有 $k$ 个关键点都不在环上。关键点编号 $1\sim k$。
问，最少需要删多少条边？

$\texttt{Data Range:}1\le k\le n\le 10^6,1\le m\le 2\times 10^6$

并查集判环，先扫一遍，只考虑两个端点都大于 $k$ 的边，维护并查集。

再扫一遍，剩下的至少有一个端点 $\le k$ 的边如果加进去发现有环，那么删除这条边一定是最优的。这个地方不好证明导致考试的时候没人敢写。

不会证明就考虑 hack 这个做法。hack 的想法肯定是删除一条边同时破坏两个环。

似乎可以构造这样的 hack 数据：

1
2
3
4
5
6
7
8
6 7 2
5 6
1 5
2 6
3 5
4 6
1 2
3 4

构造这个数据的本意是删除 $5\leftrightarrow 6$ 的这条边破坏两个环 $1\leftrightarrow 2\leftrightarrow 5\leftrightarrow 6$ 和 $3\leftrightarrow 4\leftrightarrow 5\leftrightarrow 6$。所以这样真的 hack 了吗？

我们发现即使删了这条边还是有 $1\leftrightarrow 2\leftrightarrow 5\leftrightarrow 3\leftrightarrow 4\leftrightarrow 6$ 这个更大的环……

如果删了一条边同时破环两个环，那么意味着这条边同时在两个环上，也就是说这两个环有两个点是相同的。

有两个点相同？那这两个环不就可以形成一个更大的环了！并且这个环还不依赖这条边。

所以我们感性理解一下终于敢写代码了（

点击显示/隐藏代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>

int fa[1000005], from[2000005], to[2000005];
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}

int main() {
	int n, m, k, ans = 0;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= m; ++ i) scanf("%d%d", from + i, to + i);
	for (int i = 1; i <= n; ++ i) fa[i] = i;
	for (int i = 1; i <= m; ++ i)
		if (from[i] > k && to[i] > k) fa[find(from[i])] = find(to[i]);
	for (int i = 1; i <= m; ++ i) {
		if (from[i] > k && to[i] > k) continue;
		if (find(from[i]) == find(to[i])) ++ ans;
		fa[find(from[i])] = find(to[i]);
	}
	printf("%d", ans);
	return 0;
}

$B$

给你一颗 $n$ 个节点的无根树，找出 $k$ 条路径覆盖尽量多的节点。

$\texttt{Data Range:} 1\le n\le 10^6$

有一个显而易见的贪心，每条路径起始端点一定是叶子节点。类似拓扑排序的过程，先将所有叶子入队，然后将队首元素删除，将新的没有儿子的节点入队。设拓扑序第 $i$ 层的节点有 $a_i$ 个，则答案就是 $\sum\limits^{i\le n}_{i=1}\min(2\times k,a_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
#include <cstdio>
#include <queue>

inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt;
} e[2000005];
int head[1000005], fa[1000005], deg[1000005], cnt[1000005], tot;
int d[1000005];
std::queue<int> Q;
inline void AddEdge(int u, int v) {
	e[++ tot].to = v, e[tot].nxt = head[u], head[u] = tot;
}

int main() {
	int n, k, ans = 0;
	scanf("%d%d", &n, &k);
	for (int i = 1; i < n; ++ i) {
		int u, v;
		scanf("%d%d", &u, &v);
		++ deg[u], ++ deg[v];
		AddEdge(u, v), AddEdge(v, u);
	}
	for (int i = 1; i <= n; ++ i)
		if (deg[i] == 1) Q.push(i), ++ cnt[d[i] = 1], -- deg[i];
	while (Q.size()) {
		int u = Q.front();
		Q.pop();
 		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			if ((-- deg[v]) == 1)
				Q.push(v), ++ cnt[d[v] = d[u] + 1];
		}
	}
	for (int i = 0; i <= n; ++ i) ans += min(2 * k, cnt[i]);
	printf("%d\n", ans);
	return 0;
}

$C$

魔杖护法Freda融合了四件武器，于是魔杖顶端缓缓地生出了一棵四叶草，四片叶子幻发着淡淡的七色光。圣剑护法rainbow取出了一个圆盘，圆盘上镶嵌着 $n$ 颗宝石，编号为 $0\sim n-1$。第 $i$ 颗宝石的能量是 $a_i$。如果 $a_i>0$，表示这颗宝石能量过高，需要把 $a_i$ 的能量传给其它宝石；如果 $a_i$，表示这颗宝石的能量过低，需要从其它宝石处获取 $-a_i$ 的能量。保证 $\sum a_i=0$。只有当所有宝石的能量均相同时，把四叶草魔杖插入圆盘中央，才能开启超自然之界的通道。
不过，只有M对宝石之间可以互相传递能量，其中第i对宝石之间无论传递多少能量，都要花费Ti的代价。探险队员们想知道，最少需要花费多少代价才能使所有宝石的能量都相同?

$\texttt{Data Range:}1\le n\le 16$

状压 dp 套个 MST。

$dp_s$ 表示将 $s$ 集合中所有宝石能量变为 $0$ 的最小花费。显然有 $dp_s=\min(dp_{s0}+dp_{s\setminus s0})$。再对 $s$ 集合单独跑一遍 MST。

看到这种数据范围和集合还有 MST 就想成了才学的斯坦纳树，令人谔谔的是斯坦纳被卡了，考完后狂笑不止，肥肠开心。

点击显示/隐藏代码
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
#include <cstdio>
#include <algorithm>

const int INF = 1e9;
inline int min(const int x, const int y) {return x < y ? x : y;}
struct Edge {
	int to, nxt, w;
} e[2505];
struct Node {
	int u, v, w;
	inline bool operator < (const Node x) const {return w < x.w;}
} edge[2505];
int head[20], dp[1 << 16], a[20], sum[1 << 16], fa[20], tot, tot2, n, m, k;
int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
inline void AddEdge(int u, int v, int w) {
	e[++ tot].to = v, e[tot].w = w, e[tot].nxt = head[u], head[u] = tot;
}

int kruskal(int S) {
	tot2 = 0;
	int s = 0;
	for (int i = 1; i <= n; ++ i) fa[i] = i;
	for (int i = 1; i <= n; ++ i) if (S & 1 << i - 1) {
		++ s;
		for (int j = head[i]; j; j = e[j].nxt)
			if (S & 1 << e[j].to - 1)
				edge[++ tot2].u = i, edge[tot2].v = e[j].to, edge[tot2].w = e[j].w;
	}
	std::sort(edge + 1, edge + tot2 + 1);
	int cnt = 0, ans = 0, k = 0;
	while (cnt < s - 1) {
		if ((++ k) > tot2) return 0x3fffffff;
		int fx = find(edge[k].u), fy = find(edge[k].v);
		if (fx != fy) ++ cnt, ans += edge[k].w, fa[fx] = fy;
	}
	return ans;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++ i) scanf("%d", a + i);
	for (int i = 1; i <= m; ++ i) {
		int u, v, w;
		scanf("%d%d%d", &u, &v, &w);
		++ u, ++ v;
		AddEdge(u, v, w), AddEdge(v, u, w);
	}
	for (int S = 1; S < 1 << n; ++ S)
		for (int i = 1; i <= n; ++ i)
			if (S & 1 << i - 1) sum[S] += a[i];
	for (int S = 1; S < 1 << n; ++ S) {
		if (sum[S] == 0) dp[S] = kruskal(S);
		else dp[S] = 0x3fffffff;
		for (int S0 = S & S - 1; S0; S0 = S0 - 1 & S)
			dp[S] = min(dp[S], dp[S0] + dp[S ^ S0]);
	}
	if (dp[(1 << n) - 1] <= INF) printf("%d\n", dp[(1 << n) - 1]);
	else puts("Impossible");
	return 0;
}

$D$

何老板有 $n$ 个俄罗斯套娃，编号 $1\sim n$。
每个套娃从外部看，都有一定的体积，$i$ 号套娃的外部体积为 $A_i$
每个套娃内部是空的，有一定的容积，$i$ 号套娃的内部容积为 $B_i$

对于两个套娃，若 $A_i\le B_j$ 那么 $i$ 号套娃可以套在 $j$ 号套娃内。此时，$j$ 号套娃剩余的内部体积为 $B_j-A_i$。

何老板套了一些套娃，设这些套娃从内到外编号为 $i_1,i_2…i_k$，则剩余体积为 $B_{i_1}+(B_{i_2}-A_{i_1})+…+(B_{i_k}-A_{i_{k-1}})$

何老板想选若干套娃套起来，使得剩余的体积要最小，且剩余的其他套娃无法再从最外面套上去或套进最内部。设该最小剩余体积为 $MinV$。
问，使得剩余体积为 $MinV$ 的不同方案有多少种？请你帮他计算。 $\mod 10^9+7$后再输出。

$\texttt{Data Range:}1\le n\le 2\times 10^5$

神奇图论题。

如果套娃 $i$ 能套下套娃 $j$，从 $i$ 向 $j$ 连一条边权为 $B_i-A_j$ 的边。

如果套娃 $i$ 不能被任何套娃套下，从超级源 $s$ 向 $i$ 连一条边权为 $0$ 的边。

如果套娃 $i$ 谁也套不进去，从 $i$ 向超级汇 $t$ 连一条边权为 $B_i$ 的边。

求一个最短路方案数即可。由于图是 DAG 可以跑记搜。

但是暴力连边边数是 $n^2$ 级别的，无法承受。考虑线段树优化建图，为了不写恶心的权值线段树和离散化，把所有套娃按 $A_i$ 从小到大排序。

从左往右扫，对于第 $i$ 个套娃，二分出左边最后一个 $A_j\le B_i$ 的 $j$，则问题变成了 $i\rightarrow [1,j-1]$ 连边。线段树优化建图就行了。

还有 dp 做法，但其实就是把图论的 $dis$ 数组换成 $dp$ 数组，常数会小亿些，本质是一样的，就不讲了（

点击显示/隐藏代码
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
#include <cstdio>
#include <algorithm>
#include <cstring>

inline int max(const int x, const int y) {return x > y ? x : y;}
const int mod = 1e9 + 7;
struct Edge {
	int to, nxt, w;
} e[8000005];
struct Toy {
	int a, b;
	inline bool operator < (const Toy x) const {return a < x.a;}
} toy[200005];
inline bool operator < (const int x, const Toy y) {return x < y.a;}
struct Node {
	int l, r;
} tree[800005];
int head[1000005], dis[1000005], cnt[1000005], n, tot;
bool vis[1000005];
inline void AddEdge(int u, int v, int w) {
	e[++ tot].to = u, e[tot].w = w, e[tot].nxt = head[v], head[v] = tot;//由于要跑记搜所以建的是反图
}
void make_tree(int O, int L, int R) {
	tree[O].l = L, tree[O].r = R;
	if (L != R) {
		int mid = L + R >> 1;
		AddEdge(n + O, n + O + O, 0);
		AddEdge(n + O, n + O + O + 1, 0);
		make_tree(O << 1, L, mid);
		make_tree(O << 1 | 1, mid + 1, R);
	} else AddEdge(n + O, L, -toy[L].a);
}
void update(int O, int L, int R, int p) {
	if (L > R) return;
	if (L <= tree[O].l && tree[O].r <= R) {
		AddEdge(p, n + O, toy[p].b); return;
	}
	int mid = tree[O].l + tree[O].r >> 1;
	if (L <= mid) update(O << 1, L, R, p);
	if (mid < R) update(O << 1 | 1, L, R, p);
}

void dfs(int u) {
	if (vis[u]) return;
	vis[u] = true;
	for (int i = head[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		dfs(v);
		if (dis[v] + e[i].w < dis[u]) dis[u] = dis[v] + e[i].w, cnt[u] = cnt[v];
		else if (dis[v] + e[i].w == dis[u]) cnt[u] = (cnt[u] + cnt[v]) % mod;
	}
}

int main() {
	int mxbi = 0;
	scanf("%d", &n);
	for (int i = 1; i <= n; ++ i)
		scanf("%d%d", &toy[i].a, &toy[i].b), mxbi = max(mxbi, toy[i].b);
	std::sort(toy + 1, toy + n + 1);
	make_tree(1, 1, n);
	for (int i = 1; i <= n; ++ i)
		update(1, 1, std::upper_bound(toy + 1, toy + n + 1, toy[i].b) - toy - 1, i);
	for (int i = 1; i <= n; ++ i)
		if (mxbi < toy[i].a) AddEdge(0, i, 0);
	for (int i = 1; i <= n; ++ i)
		if (toy[i].b < toy[1].a) AddEdge(i, 5 * n + 1, toy[i].b);
	memset(dis, 0x3f, sizeof dis);
	vis[0] = true, dis[0] = 0, cnt[0] = 1;
	dfs(5 * n + 1);
	printf("%d", cnt[5 * n + 1]);
}
-------------本文结束感谢您的阅读-------------