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

· · 题解

这有点色情了吧。

一个分层图最短路的解法，个人认为挺好想的。

本文连通块指将有向边视为无向边后的连通块。

首先，因为每次图都是原来的图，那么很显然，每个点能达到的最大值绝对是该连通块的最大值。

你会发现，因为这个交换是有传递性的，所以假如你想从 i\to j 且最短路上经过了 a_{1\sim k}，那么不存在一个 i 满足将有向边看作无向边时，a_i 可抵达 a_{i+2}。

然后我们就钦定连通块内只有一个最大值，那么从最大值经过的点来考虑，假设路上经过了 a_{1\sim k}，绝对是有假如 a_i 能顺着边到达 a_{i+1}，a_{i+2} 也能顺着边到达 a_{i+1}，且 a_{i+2} 顺着边到达 a_{i+3}。

考虑假如 a_i 不能顺着边到达，那么将图中所有边翻转方向后，a_i 能顺着边到达 a_{i+1}。

然后你会发现一个更惊人的事实，假如 a_i 要交换到 a_{i+1}，可以视作经过若干次交换一条边两边的元素且不耗次数，最后将次数 +1。

那么也就是说我们建个将边翻转的图，然后你假如在一个点，你去另外一个图的代价为 1（即终止这次交换），这样可以视作 i 和另外一张图的 i 连一条边权为 1 的无向边，且两张图上的边权都为 0。。

那么假如我们知道了一个连通块的所有最大值位置，那么思路就有了，建出刚刚说的图，然后以所有最大值位置为起点，跑一遍多源最短路（当然边权为 01 所以也可以跑一遍 01 bfs）。

找到一个连通块的所有最大值位置可以直接并查集即可。

时间复杂度 O((n+m)\log n)，瓶颈在于 dij，当然可以 01 bfs 做到 O(n \alpha(n)+m)，此时瓶颈在并查集。但是还可以直接搜出所有连通块做到 O(n+m)。反正我常数较小可以 \log 过。

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>

const int N=1e6+5;
int n,m,p[N];
vector<pii> e[N];
int d[N],mx[N];
int find(int x){
    if(x==d[x]) return x;
    else return d[x]=find(d[x]);
}
int dis[N],vis[N];

void dij(){
    priority_queue<pii,vector<pii>,greater<pii>> qp;
    fill(dis+1,dis+2*n+1,1e9);
    for(int i=1;i<=n;i++) if(p[i]==mx[find(i)]){
        qp.push({0,i});
        qp.push({0,n+i});
        dis[i]=dis[n+i]=0;
    }
    while(!qp.empty()){
        int f=qp.top().second;qp.pop();
        if(vis[f]) continue;
        vis[f]=1;
        for(pii i:e[f]){
            if(dis[i.first]>dis[f]+i.second){
                dis[i.first]=dis[f]+i.second;
                qp.push({dis[i.first],i.first});
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>p[i];
    for(int i=1;i<=n;i++) d[i]=i;
    for(int i=1,u,v;i<=m;i++){
        cin>>u>>v;
        e[u].push_back({v,0});
        e[v+n].push_back({u+n,0});
        d[find(u)]=find(v);
    }
    for(int i=1;i<=n;i++) e[i].push_back({i+n,1}),e[i+n].push_back({i,1});
    for(int i=1;i<=n;i++) mx[find(i)]=max(mx[find(i)],p[i]);
    dij();
    for(int i=1;i<=n;i++) {
        if(p[i]==mx[find(i)]) cout<<0<<' ';
        else cout<<1+min(dis[i],dis[n+i])<<' ';
    }
    return 0;
}