题解：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$ 过。~~

CPP

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

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

文章操作

相关推荐

评论

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