LOJ#3346 [APIO2020]交换城市

博主： tony102
发布时间：2021 年 05 月 18 日
1563 次浏览
暂无评论
1466字数
分类：题解

[Luogu6765](https://www.luogu.com.cn/problem/P6765)

还是推荐用 LOJ 评测,可以评测全部的数据

[LOJ3346](https://loj.ac/p/3346)

## Description

给一个简单一些的题面

有一张 $n$ 个点 $m$ 条边的带权无向图, 均从 $0$ 开始编号.现在有 $Q$ 组询问,每次两个人从 $u,v$ 出发,要求这两个人不能同时在一个点上,也不能同时经过一条边.允许多次走一个点或者一条边.

现在要求最小化路径上的最大边权.

## Sol

APIO2021来之前决定做一些 APIO 的真题来练练手

APIO 的题都是用实现函数类似于交互库的形式, 还是要提前适应

首先看到最小化最大这种东西,可以先试着往二分上靠.那么就二分这个答案最大权,每次两个点丢进去暴跳的途中判断就完事儿了.可能要注意下细节.应该可以拿到 Subtask3 的部分分

现在二分判定的瓶颈不在二分出答案上面,而是在判定答案时我是爆判的.考虑来优化这个过程.最简单的情形就是在一条链上面,这个两个人如果同时往中间跳时相遇,就跑不掉了.这样链的答案是 $-1$ . 菊花图的情况对应 Subtask2, 那么只需要判断一下起点和终点经不经过菊花根就可以了.

现在要解决的问题就是什么时候一定会有答案. 已知链无解,无解是因为必要同时经过同一边.但凡有一条别的出边能出去,就有可能有解. 假如现在有这么一条边能让它出去了,要再让他回来到达终点就必须有一条边引回.这样就是一个三元环.(这个过程可以多画画图)

解决了这个问题,二分的方法复杂度是 $O(Qn \log n)$ .可以通过 Subtask4

解决问题的关键又变成了二分不够优秀.考虑 Kruskal 重构树.可以用来解决这个问题. 在 Kruskal 重构树上, $u, v$ 路径上的最小被阀值限制的边权就是它们 lca 的点权.

还有一个问题就是做 Kruskal 的时候还要注意连通块是不是链的问题.可以这么解决,同时维护一个连通块的起点和终点,以及连通块的一个根.合并的时候注意,分情况讨论.

1. 现在两个连通块要合并,不是链的话合并以后也不是
2. 还不能合并: 
   1. 有一个不是新的就不是
   2. 原来两个都是链,那么就看是不是两条链的端点连边,如果是的话就会连成一条链.

## Code

Luogu 的不要加 `swap.h` 这一句

```cpp
#include <bits/stdc++.h>
#include "swap.h"

const int SIZE = 3e5 + 5;

int num, idx, tim, n;
int head[SIZE], vis[SIZE], w[SIZE], st[SIZE], ed[SIZE], fa[SIZE], dfn[SIZE], root[SIZE], f[SIZE][21];

std::vector < int > chain[SIZE];

struct node {
	int to, nxt;
} edge[SIZE << 1];

struct E {
	int from, to, v;

bool operator< (const E a) const {
		return v < a.v;
	}
} e[SIZE];

void addEdge(int u, int v) {
	edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }

void dfs(int u, int anc) {
	dfn[u] = ++ idx;
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == anc) continue;
		f[v][0] = u, root[v] = !u ? 0 : root[u];
		for (int j = 1; j <= 20; ++ j) f[v][j] = f[f[v][j - 1]][j - 1];
		// printf("from:%d to:%d\n", u, v);
		dfs(v, u);
	}
}

void init(int N, int M, std::vector < int > U, std::vector < int > V, std::vector < int > W) {
	int tot = 0; tim = N, n = N;
	for (int i = 1; i <= M; ++ i) e[i].from = U[i - 1] + 1, e[i].to = V[i - 1] + 1, e[i].v = W[i - 1];
	std::sort(e + 1, e + M + 1);
	for (int i = 1; i <= N; ++ i) fa[i] = i, st[i] = ed[i] = root[i] = i, chain[i].push_back(i);
	for (int i = 1; i <= M; ++ i) {
		int x = e[i].from, y = e[i].to;
		int fx = find(e[i].from), fy = find(e[i].to); tim = i + N;
		if (chain[fx].size() < chain[fy].size()) { std::swap(x, y); std::swap(fx, fy); }
		if (fx == fy) {
			if (!vis[fx]) {
				vis[fx] = 1;
				for (auto it: chain[fx]) addEdge(tim, it);
				root[fx] = tim;
			}	
		}
		else {
			if (vis[fx] || vis[fy]) {
				if (vis[fx]) addEdge(tim, root[fx]);
				else for (auto it: chain[fx]) addEdge(tim, it);
				if (vis[fy]) addEdge(tim, root[fy]);
				else for (auto it: chain[fy]) addEdge(tim, it);
				vis[fx] = 1, root[fx] = tim, fa[fy] = fx;
			}
			else {
				if ((x == st[fx] || x == ed[fx]) && (y == st[fy] || y == ed[fy])) {
					st[fx] = x ^ st[fx] ^ ed[fx], ed[fx] = y ^ st[fy] ^ ed[fy];
					for (auto it: chain[fy]) chain[fx].emplace_back(it);
					fa[fy] = fx;
				}
				else {
					vis[fx] = 1; 
					for (auto it: chain[fx]) addEdge(tim, it);
					for (auto it: chain[fy]) addEdge(tim, it);
					fa[fy] = fx, root[fx] = tim;
				}
			}
		}
	}
	for (int i = N + M; i; -- i) {
		if (!dfn[i]) dfs(i, 0);
	}
	// for (int i = 1; i <= N + M; ++ i) {
	// 	printf("from:%d ", i);
	// 	for (int j = 1; j <= 5; ++ j) printf("%d ", f[i][j]);
	// 	puts("");
	// }
}

int lca(int u, int v) {
	if (u == v) return u;
	if (root[u] != root[v]) return -1;
	if (dfn[u] > dfn[v]) std::swap(u, v);
	for (int i = 20; ~i; -- i) {
		if (dfn[f[v][i]] > dfn[u]) v = f[v][i];
	}
	return f[v][0];
}

int getMinimumFuelCapacity(int X, int Y) {
	++ X, ++ Y;
	int anc = lca(X, Y);
	if (anc == -1) return -1;
	return e[anc - n].v;
}

```

最后修改：2021 年 08 月 20 日