题解：P11352 [NOISG 2024 Finals] Coin

· · 题解

由于保证有解，所以原图是一个 DAG。

考虑拓扑序，设点 u 的拓扑序是 tpu_u。对于每个点 x 要求出最小的时间使得 \forall y\not=x，当 tpu_x<tpu_y 时，x 到 y 有一条路径，否则 y 到 x 有一条路径。

所以我们就有了一个朴素的做法，枚举每个点 x，将点集分为拓扑序大于 tpu_x，拓扑序小于 tpu_x，再用上述做法完成即可。

只考虑拓扑序小于 tpu_x 的点，大于的是同理的。

用路径来刻画我们依旧不好做，可以发现我们只用判是否是 DAG，而 DAG 满足：对于 3 个点 u,v,w，如果 u 到 v 有一条路径，v 到 w 有一条路径，那么 u 到 w 显然也有一条路径。所以我们不难看出拓扑图的充要条件可以转成这样：所有拓扑序 <tpu_x 的点都有一条出边的拓扑序也 \le tpu_x 的边。

接着最小化时间，可以直接贪心，每个点记录满足上述条件的、时间最小的值即可。

时间复杂度单 \log。

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fir first
#define sec second
#define mk make_pair
using namespace std;
inline int read(){
    int x=0;bool f=0;char ch=getchar();
    while(ch<'0'||ch>'9')f^=(ch=='-'),ch=getchar();
    while('0'<=ch&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int Maxn=8e5+5,inf=1e9+7;
int n,m;
struct edge{
    int u,v;
}e[Maxn];
int du[Maxn],f[Maxn];
int ans[Maxn];
vector<pii>G1[Maxn];
vector<int>G[Maxn];
multiset<int>s;
int tpu[Maxn];
inline void sol1(){
    memset(f,0x3f3f,sizeof f);
    s.clear();
    for(int i=1;i<=m;i++){
        du[e[i].v]++;
        G[e[i].u].emplace_back(e[i].v);
        G1[e[i].v].emplace_back(mk(e[i].u,i));
    }
    queue<int>h;
    for(int i=1;i<=n;i++)if(!du[i])h.push(i);
    int cnt=0;
    while(!h.empty()){
        int u=h.front();h.pop();
        tpu[++cnt]=u;
        for(pii it:G1[u]){
            int y=it.fir;
            s.erase(s.find(f[y]));f[y]=min(f[y],it.sec);s.insert(f[y]);
        }if(!s.empty())ans[u]=(*s.rbegin());
        for(int y:G[u]){
            if(!(--du[y]))h.push(y);
        }s.insert(f[u]);
    }
}

inline void sol2(){
    memset(f,0x3f3f,sizeof f);
    for(int i=1;i<=n;i++)G1[i].clear();
    for(int i=1;i<=m;i++)G1[e[i].u].emplace_back(mk(e[i].v,i));
    s.clear();
    for(int i=n;i;i--){
        int u=tpu[i];
        for(pii it:G1[u]){
            int y=it.fir;
            s.erase(s.find(f[y]));f[y]=min(f[y],it.sec);s.insert(f[y]);
        }if(!s.empty())ans[u]=max(ans[u],(*s.rbegin()));
        s.insert(f[u]);
    }
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    n=read();m=read();
    for(int i=1;i<=m;i++)e[i]={read(),read()};

    sol1();
    sol2();

    for(int i=1;i<=n;i++)printf("%d ",(ans[i]>m?-1:ans[i]));
    return 0;
}
/*
7 20
1 6
6 3
1 4
1 5
1 7
1 2
1 5
2 3
4 5
7 2
2 4
5 3
6 3
1 3
4 3
7 5
2 6
4 6
7 2
7 5

4 4
2 4
3 1
4 1
2 3
*/