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

· · 题解

前置知识：多源 bfs，连通块。

题目描述

给定一张 n 个点，m 条边的有向图，点从 1 \sim n 编号。图中每个点 i 有点权 p_i。注意可能有重边自环。

如果点 u 出发存在路径到达点 v，则你可以将 u,v 的点权交换。

对于每个点 i，输出使 i 点权最大化的最少交换次数。请注意，每个回答是独立的，即都应该从初始给定的图开始交换。

思路

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

引理 1

若将所有有向边转成无向边后，图会被分成若干个连通块。对于每个连通块上的点，都存在最大权值 P，则该连通块上的所有点均可通过若干步将权值转化为 P，且 P 就是该连通块上的点能转化出来的最大权值。

大家自己思考便可得到，这里就不证明了。

现在考虑在每个连通块里面 bfs，求出最少交换次数。

那么这个路径长度怎么求呢？

引理 2

显然同方向路径长度不加，不同方向路径长度加 1。

这里举个简单例子来方便大家理解。

有 5 个点 1,2,3,4,5，权值也是 1,2,3,4,5，节点编号和权值相等，如下图。

因为转成无向图后是连通的，所以每个点的权值都可以转化为 5。

我们发现 5 到 3 的路径和 2 到 3 的路径方向相反，所以节点 2 需要的次数比节点 3 多 1。而 1 到 2 的路径和 2 到 3 的路径方向相同，所以节点 1 的次数等于节点 2 的次数，不用加 1。

我们可以建正图和反图，方便我们反向 bfs。

可以建立一个数组 dis[N][2]（0 表示正边，1 表示反边），最后 i 的答案即为 \min(dis_{i,0},dis_{i,1})。

代码

#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;
}