【0】做题心得 - 2025 NOIP #67 - T2 / 题解：P13118 [GCJ 2019 #2] Contransmutation【Tarjan】【图论】【缩点】【动态规划】

· · 题解

如此成绩，何以 PION。你首先考虑一个无限的情况是怎么样的。你会发现在强连通分量里面有完全なるの黄金回旋エネルギー，可以无限传递。当这个 SCC 内的边数与点数相等时就显然有每个点最大为他们的和。要是边数更多一点，就显然有无限传递。缩点后这就显然是一个 DAG，直接做即可。注意判断 0，也就是没有病毒的情况。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=2e5+10;
const ll P=1e9+7;
ll d[N]; bool z[N];
int n,a[N],cnt[N],deg[N];
int id[N],low[N],ic;
int sid[N],stk[N],top,sd,sz[N];
vector<int>e[N],g[N],nd[N];
bool vis[N];
void tarjan(int p){
    stk[++top]=p;
    id[p]=low[p]=++ic;
    for(auto v:e[p]){
        if(!id[v]){
            tarjan(v);
            low[p]=min(low[p],low[v]);
        }else if(!sid[v])
            low[p]=min(low[p],id[v]);
    }
    if(low[p]==id[p]){
        ++sd;
        int q=stk[top];
        do{
            q=stk[top], --top;
            sid[q]=sd;
            sz[sd]++;
            d[sd]=(d[sd]+a[q])%P;
            z[sd]=z[sd]|bool(a[q]);
            nd[sd].push_back(q);
        }while(p!=q);
    }
    return;
}
queue<int>q;
int main(){
    freopen("virus.in","r",stdin);
    freopen("virus.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int u,v;
        cin>>u>>v;
        e[i].push_back(u);
        e[i].push_back(v);
    }
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)if(!id[i])
        tarjan(i);
    for(int i=1;i<=n;i++)for(auto v:e[i])
        if(sid[i]==sid[v]) cnt[sid[i]]++;
        else g[sid[i]].push_back(sid[v]), deg[sid[v]]++;
    for(int i=1;i<=sd;i++)
        if(!deg[i]) q.push(i);
    while(q.size()){
        int p=q.front();
        q.pop();
        if(cnt[p]>sz[p]&&z[p]) d[p]=-1;
        for(auto v:g[p]){
            z[v]=z[v]|z[p];
            if(d[p]==-1||d[v]==-1||(cnt[p]==sz[p]&&z[p])) d[v]=-1;
            else d[v]=(d[v]+d[p])%P;
            if(!(--deg[v])) q.push(v);
        }
    }
    for(int i=1;i<=n;i++)
        cout<<d[sid[i]]<<" ";
    return 0;
}