题解 P4974 【毒瘤之神秘通道】

· · 题解

自己的题怎么能不发篇题解呢qwq
（出题人自己觉得实际上可以用树剖的）
然后CYJian大佬一看：

“这不就是两遍拓补排序吗....”

经过了这段话后...我是豁然开朗...... 

#include <bits/stdc++.h>
#define reg register
#define ge getchar()
#define Num(a) isdigit(a)
#define maxn 2000000
inline long long read() {
    reg long long x = 0, ch = ge;
    while(!Num(ch)) ch = ge;
    while(Num(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = ge;
    return x;
}
inline long long min(long long a,long long b){return a>b?b:a;}
int n, m,from[maxn + 1],gotoo[maxn + 1];
long long dis[maxn + 1],s[maxn + 1],q[maxn + 1];
int main() {
    n = read(), m = read();
    for(reg int i=1;i<=n;i++) 
        ++from[gotoo[i]=read()];
    for(reg int i=1;i<=m;i++) 
        ++from[gotoo[i+n]=read()],dis[i+n]=read();
    reg int x,L=1,R=0,Top=0;
    for(x=1;x<=m;++x) 
        q[++R] = x + n;
    for(x=1;x<=n;++x) 
        if(!from[x])q[++R]=x;
    while(L<=R) {
        s[++Top] = x = q[L++];
        if(!gotoo[x]) continue;
        --from[gotoo[x]];
        if(!from[gotoo[x]]) q[++R]=gotoo[x];
        dis[gotoo[x]]+=dis[x];
    }
    while(gotoo[s[Top]]==0)--Top;
    while(Top)x=s[Top--],dis[x]+=dis[gotoo[x]];
    reg long long res=2147483647LL*2147483647LL;
    reg int pos = 0;
    for(reg int i = 1; i <= m; i++) {
        res=min(res,dis[gotoo[i+n]]);
        if(dis[gotoo[i+n]]==res)
            pos=gotoo[i+n];
    }
    printf("%d %lld", pos, res);
    return 0;
}

代码略丑请见谅....