专栏文章

题解：P13823 「Diligent-OI R2 C」所谓伊人

yyezicong1104
P13823题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio613rp
此快照首次捕获于
2025/12/02 13:56
3 个月前
此快照最后确认于
2025/12/02 13:56
3 个月前
查看原文
前置知识：多源 bfs，连通块。

题目描述

给定一张 nn 个点，mm 条边的有向图，点从 1∼n1 \sim n 编号。图中每个点 ii 有点权 pip_i。注意可能有重边自环。
如果点 uu 出发存在路径到达点 vv，则你可以将 u,vu,v 的点权交换。
对于每个点 ii，输出使 ii 点权最大化的最少交换次数。请注意，每个回答是独立的，即都应该从初始给定的图开始交换。

思路

因为若存在 u→vu \to v 的路径，则可将 u,vu,v 的点权交换。同理若存在 v→uv \to u 的路径，也可以交换 u,vu,v 的点权。

引理 1

若将所有有向边转成无向边后，图会被分成若干个连通块。对于每个连通块上的点，都存在最大权值 PP，则该连通块上的所有点均可通过若干步将权值转化为 PP，且 PP 就是该连通块上的点能转化出来的最大权值。
大家自己思考便可得到，这里就不证明了。
现在考虑在每个连通块里面 bfs，求出最少交换次数。
那么这个路径长度怎么求呢？

引理 2

显然同方向路径长度不加，不同方向路径长度加 11。
这里举个简单例子来方便大家理解。
有 55 个点 1,2,3,4,51,2,3,4,5，权值也是 1,2,3,4,51,2,3,4,5，节点编号和权值相等，如下图。
因为转成无向图后是连通的，所以每个点的权值都可以转化为 55。
  • 节点 55 的权值最大，需要经过 00 此交换。
  • 节点 33 可以和节点 55 的权值交换，需要一步。
  • 节点 44 和节点 55 不能一次到达，所以要先交换 33 和 55 的权值，再交换 33 和 44 的权值，需要两次。
  • 同理节点 22 也需要两次。
  • 节点 11 和节点 33 可达，所以先交换 1,31,3，再交换 3,53,5，需要 22 次。
我们发现 55 到 33 的路径和 22 到 33 的路径方向相反，所以节点 22 需要的次数比节点 33 多 11。而 11 到 22 的路径和 22 到 33 的路径方向相同，所以节点 11 的次数等于节点 22 的次数，不用加 11。
我们可以建正图和反图，方便我们反向 bfs。
可以建立一个数组 dis[N][2]（00 表示正边，11 表示反边），最后 ii 的答案即为 min⁡(disi,0,disi,1)\min(dis_{i,0},dis_{i,1})。

代码

CPP
#include <bits/stdc++.h>
using namespace std;

const int N = 500010, M = 1000010;

int n, m, k;
int p[N];
int head[N], e[M], ne[M], idx, rhead[N]; // 存边
int dis[N][2];
bool vis[N];
vector<int> v[N]; // 存储连通块
queue<pair<int, int> > q;

void add(int *h, int a, int b) {
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
// 遍历连通块
void dfs(int x) {
	vis[x] = 1, v[k].push_back(x);
	for (int i = head[x]; i; i = ne[i]) { // 正边
		int j = e[i];
		if (!vis[j]) dfs(j);
	}
	for (int i = rhead[x]; i; i = ne[i]) { // 反边
		int j = e[i];
		if (!vis[j]) dfs(j);
	}
}
// 拓展所有同方向的点
void f(int x, int *h, int d,int p) {
	for (int i = h[x]; i; i = ne[i]) {
		int j = e[i];
		if (dis[j][p] == 0x3f3f3f3f) {
			dis[j][p] = d;
			q.push({j, p});
			f(j, h, d,p);
		}
	}
}
// 多源最短路
void bfs(int x) {
	int maxx = 0;
	for (int i : v[x]) maxx = max(maxx, p[i]); // 求最大权值
	for (int i : v[x])
		if (p[i] == maxx) {
			dis[i][0] = dis[i][1] = 0;
			q.push({i, -1}); // 起点是-1
		}
	while (q.size()) {
		auto [u, p] = q.front();
		q.pop();
        if (p == 0) { // 正边
            f(u, head, dis[u][p], 0); // 同向不变
    		f(u, rhead, dis[u][p] + 1, 1); // 不同向+1
        } else if (p == 1) { // 反边
            f(u, head, dis[u][p] + 1, 0);
    		f(u, rhead, dis[u][p], 1);
        } else { // 起点必+1
            f(u, head, dis[u][0] + 1, 0);
    		f(u, rhead, dis[u][0] + 1, 1);
        }
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
	while (m--) {
		int u, v;
		scanf("%d%d", &u, &v);
		if (u == v) continue;
		add(head, u, v), add(rhead, v, u); // 正向建边，反向建边
	}
	for (int i = 1; i <= n; i++)
		if (!vis[i])
			k++, dfs(i); // 处理连通块
	memset(dis, 0x3f, sizeof dis); // 赋极大值
	for (int i = 1; i <= k; i++) bfs(i);
	for (int i = 1; i <= n; i++) printf("%d ", min(dis[i][0], dis[i][1])); // 取最小值
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...