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

ylch · 2025-08-24 20:04:49 · 题解

讨论区中有很多有用的 hack，没过的话可以去看看。

每个点都可以换到其所在弱连通分量的最大点权，这是毋庸置疑的。

为了方便陈述，下文中记当前弱连通分量中点权最大的点为 x，点 u 的最终答案为 ans[u]。

考虑一个点 u 的交换过程，可能有以下几种情况：

不难想到，权值在不断转移的过程其实可以看成联通分量中点 x 通过一条路径走到一些待更新点的过程，我们想求最小操作次数其实就是求 x 到其他点的最短路。现在的问题是如何合理安排边的方向和权值。

先考虑边的方向。

对于情况二，如果建原图的反图，那么方向显然就对上了（可以从 x 向待操作的点走）。

思考对于情况三怎么办，我们定义“正向边”为与原图方向相反的边，“反向边”为与原图方向相同的边。

注：这样定义正向、反向边是相对于点 x 而言，看起来方便一些。

发现“中转”过程其实可以用若干套正向边（与原图方向相反）和反向边（和原图方向相同）来刻画。具体地，假设当前点为 u，那么转移路径应该是 x \xrightarrow{\text{正向边}} v \xrightarrow{\text{反向边}} u。

下面考虑边的权值，或者说考虑如何求答案。

首先想到的是可以每中转一次答案就加 1。这显然是对的，但太麻烦了，因为每个点的来源都不同，也不确定会经过几次中转，过程中还要维护边的方向等。

考虑一种更简单的分层图方法：一层是原图，另一层是反图，这些边权都是 0。然后上下每个对应的点建一个边权为 1 的双向边（相当于把中转时的花费放到层与层之间的转换上）。

然后，我们找出所有弱连通分量中点权最大的点及其在下一层的对应点作为起点，都跑一遍最短路，因为不能确定从哪个起点走一定最优。

记 u 在下一层中的点为 u'，到 u 的最短路为 dis[u]，则 ans[u]=\min\{dis[u], dis[u']\}。

但尝试发现这样会出问题：有的结点答案少 1，有的又没少，这是为什么呢？不难发现，是因为题目无论如何都需要至少一次操作，但按照上面的方法，如果 u 能直接到 x，那么 dis[u]=0。这显然不对，那么对于能直接到达 x 的点把答案加一即可。

综上，记 u 点权为 val[u]，u 所在连通块编号为 pos[u]，连通块 p 中的最大点权为 mx[p]，答案为：

来算一下时间复杂度，dijkstra 的时间复杂度为 O(m\log n)，但这道题卡的比较紧，\log 可能会 TLE。

但考虑到本题图中边权只有 0 和 1 两种情况，可以用多源 01bfs 优化，总时间复杂度为 O(m)。

01bfs 核心是用双端队列，把边权为 0 的放到队首，边权为 1 的放到队尾，这样每次取出队首就一定是当前距离起点距离最小的点之一。本质上是根据 01 判断省掉了 dijkstra 优先队列排序的 \log。

#include <bits/stdc++.h>
using namespace std;
// 省略恶心快读部分
using pii = pair<int, int>;
const int maxn = 2 * 5e5 + 7;  // 分层图两倍空间！

int n, m, dis[maxn];           // dis存到每个点的最短路
int pos[maxn], Mx[maxn];       // 每个点所属连通块编号、每个连通块中的最大点权
vector<array<int, 2>> G[maxn]; // 存主图（有向图，分两层）
vector<int> g[maxn];           // 存无向图，用于处理弱连通分量
int ans[maxn];                 // 记录答案

struct Node{
    int val, id; // 点权、编号
}p[maxn];
bool cmp1(Node p1, Node p2){ return p1.val > p2.val; }
bool cmp2(Node p1, Node p2){ return p1.id < p2.id; }

void Input(){ // 读入数据
    read(n, m);
    for(int i = 1; i <= n; i ++){
        read(p[i].val); p[i].id = i;
        G[i].push_back({i+n, 1}), G[i+n].push_back({i, 1}); // 层间转换
    }
    for(int u, v, i = 1; i <= m; i ++){
        read(u, v);
        G[u].push_back({v, 0}), G[v+n].push_back({u+n, 0}); // 有向图：正图、反图
        g[u].push_back(v), g[v].push_back(u); // 无向图
    }
}

void getMax(){ // 找到每个弱连通分量中的最大点权
    int cnt = 0; // 连通块的计数器
    for(int i = 1; i <= n; i ++){
        if(pos[i] == 0){ // 没被访问过
            pos[i] = ++ cnt; Mx[cnt] = max(Mx[cnt], p[i].val); // 更新
            queue<int> Q; Q.push(i);
            while(!Q.empty()){
                int u = Q.front(); Q.pop();
                pos[u] = cnt; Mx[cnt] = max(Mx[cnt], p[u].val); // 更新
                for(int v : g[u]){
                    if(pos[v] == 0) Q.push(v);
                }
            }
        }
    }
}

void getPath(){ // 跑最短路 
    vector<int> vis(maxn);
    deque<int> Q; 
    memset(dis, 0x3f, sizeof dis); // 初始化为极大值
    for(int i = 1; i <= n; i ++){ // 所有是最大点权的点都可以作为起点
        if(p[i].val == Mx[pos[p[i].id]]){
            Q.push_back(p[i].id); Q.push_back(p[i].id + n); // 把两层都放入
            dis[p[i].id] = dis[p[i].id + n] = 0; // 起点dis=0
        }
    }
    while(!Q.empty()){ // 01bfs
        auto u = Q.front(); Q.pop_front();
        if(vis[u]) continue;
        vis[u] = true;
        for(auto [v, w] : G[u]){
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                if(w == 0) Q.push_front(v); // 边权为0的放前面，边权为1的放后面，时间复杂度O(m)（省去dijkstra的排序）
                else Q.push_back(v);
            }
        }
    }
}

void Output(){ // 输出
    sort(p + 1, p + n + 1, cmp2); // 再按照原来的id排序回去，下面输出
    for(int i = 1; i <= n; i ++){
        int ans = min(dis[i], dis[i + n]) + 1; // 初始答案，别忘了+1
        if(p[i].val == Mx[pos[i]]) ans = 0; // 特判：如果是最大点权那么答案为0
        cout << ans << " \n"[i == n];
    }
}

signed main()
{
    ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    Input();   // 读入
    getMax();  // 找到每个弱连通分量中的最大点权
    getPath(); // 跑最短路
    Output();  // 输出
    return 0;
}