题解：P13118 [GCJ 2019 #2] Contransmutation

Little_duck_GGG · 2026-05-11 13:55:13 · 题解

题目意思

有 m 种金属，第 i 种金属当前有 g_i 克，并给出 m 种配方。

对于第 i 种配方，都可以消耗一克第 i 种金属，变成一克 r_{i,1}，r_{i,2} 种金属。

求金属 1 的最多克数。如果无限，则输出一串莫名其妙的字符，~其实是我不知道怎么写格式~。

题目思路

首先考虑一种金属是否可以达到无限。

很容易想到，如果一个金属是无限的，那么它能生产的金属一定无限。

然后就要思考，如果一个金属无限，那么它满足什么条件。

很多人存在一个误区，就是认为假设两种金属能够相互生产，且其中一种金属非零，那么它们都能互相生产。~我一开始也是这么想的~。

但这样是错的。

给出一幅图就知道了。

这里假设 a 能生产 b，我们就把 a 和 b 连一条有向边。

这里 1，2 两种金属可以互相生产，即它们在一个连通块内，但是它们不是无限的吧。

因为不管两个点如何的传递，它们的值始终不变，且可以进行无限次操作。

那么既然能做无限次操作且值不变，换句话说，是不是第 3 种金属可以无限生产。

这是不是启发我们可以缩点。

如果一种金属 a 和另一种金属 b 在一个联通块内，且 a 能生产 b。

那么对于一个被 a 生产的金属 c，c 就能被无限生产，但注意 a，b 均不能无限生产。

这是一种情况。

我们再考虑一种情况。

此时 1，2，3 这三种金属应该都能无限生产吧。这很容易考虑。

那这样无限的情况就考虑完了。

注意最后要跑一遍拓扑，因为如果一个点是无限，它所指向的点也是无限的。

那么接着考虑如果不是无限怎么处理。

那这种情况应该是不难处理的，我们跑一遍拓扑排序就可以了。

但其实做到这里还没完。

你得考虑金属初始值为零的情况。

假设三个点都在一个连通块内，且此时一个点指向另外两点，但三个点的初始权值都为零，那么这样肯定不是无限。

不过如果你以为这道题就做完了，那你又错了，我再给一个图。 这幅图中，1，2，3，三个点权值为零，且 4 号点权值为 1，此时金属 1 应该是可以无限生产的吧。

但如果按照我们上面的条件判断，那么我们应该会判断 1 不是无限而是零，因为 1，2，3 都没权值。

但是这样就错了。

因为此时 1 号金属是可以被 4 号金属生产的，这启示我们应该要先跑一遍计算答案的拓扑排序，再跑判断无限的，这样就万无一失了。

一点小细节

由于这道题输出的答案是要取模的，如果一个数本来是有值，但取模完后变成零了，得特判一下。

最后给出代码

#include<bits/stdc++.h>
#define int long long
const int N=1e5+5;
using namespace std;
int t,mod=1e9+7;
int in[N],f[N];
vector<int> g[N];
int n,m;
int a[N],b[N],cnt,scc;
int dfn[N],dad[N],low[N],vis[N],s[N],tot;
int c[N],qq[N];
bool pd[N];
void tarjan(int x)//tarjan模版 
{
    vis[x]=1;
    dfn[x]=low[x]=++cnt;
    s[++tot]=x;
    for(int i=0;i<g[x].size();i++)
    {
        int y=g[x][i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(vis[y]) low[x]=min(low[x],low[y]);
    }
    if(low[x]==dfn[x])
    {
        scc++;
        do
        {
            c[scc]+=qq[s[tot]]; 
            pd[scc]|=bool(qq[s[tot]]);//记录是否真的是零 
            c[scc]%=mod;
            vis[s[tot]]=0;
            dad[s[tot]]=scc;
            tot--;
        }
        while(s[tot+1]!=x);
    }
}
int cp[N];
bool oh_no[N];
queue<int> q;
void k_s_oh_no()//跑一遍答案的拓扑 
{
    for(int i=1;i<=scc;i++) cp[i]=in[i]; 
    for(int i=1;i<=scc;i++)
    {
        if(!in[i]) q.push(i);
    }
    while(!q.empty())
    {
        int x=q.front();
        for(int i=0;i<g[x].size();i++)
        {
            c[g[x][i]]+=c[x];
            pd[g[x][i]]|=pd[x];
            c[g[x][i]]%=mod;
            in[g[x][i]]--;
            if(!in[g[x][i]]) q.push(g[x][i]);
        }   
        q.pop();
    }
}
void tp()//跑一遍判断无限的拓扑 
{
    for(int i=1;i<=scc;i++) in[i]=cp[i]; 
    for(int i=1;i<=scc;i++)
    {
        if(!in[i]) q.push(i);
    }
    while(!q.empty())
    {
        int x=q.front();
        for(int i=0;i<g[x].size();i++)
        {
            oh_no[g[x][i]]|=oh_no[x];//注意传递无限 
            in[g[x][i]]--;
            if(!in[g[x][i]]) q.push(g[x][i]);
        }   
        q.pop();
    }
}
void q_g_w_d()//清零操作 
{
    tot=scc=0;
    for(int i=1;i<=n;i++)
    {
        g[i].clear();
        dfn[i]=pd[i]=low[i]=dad[i]=vis[i]=oh_no[i]=c[i]=cp[i]=in[i]=s[i]=qq[i]=pd[i]=0;
    }
}
int iqiq;
signed main()
{   
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i]>>b[i];
            g[i].push_back(a[i]);
            g[i].push_back(b[i]);
        }
        for(int i=1;i<=n;i++) cin>>qq[i];
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i]) tarjan(i);
        }
        for(int i=1;i<=n;i++) g[i].clear();
        for(int i=1;i<=n;i++)//缩点 
        {
            int a1=dad[a[i]],b1=dad[b[i]],i1=dad[i];
            if(i1!=a1)
            {
                in[a1]++; 
                g[i1].push_back(a1);
            }
            if(b1!=i1)
            {
                in[b1]++;
                g[i1].push_back(b1);
            }
        }
        k_s_oh_no();
        for(int i=1;i<=n;i++)//一堆判断 
        { 
            if(dad[a[i]]==dad[i]&&dad[b[i]]==dad[i])//指向的两个点和自己在一个连通块里 
            {
                if(pd[dad[a[i]]]||pd[dad[b[i]]]||pd[dad[i]]) oh_no[dad[i]]=1;
            }
            if(dad[a[i]]==dad[i])//另外一种情况，这两个if类似 
            {
                if(pd[dad[a[i]]]) oh_no[dad[b[i]]]=1;
            }
            if(dad[b[i]]==dad[i])
            {
                if(pd[dad[b[i]]]) oh_no[dad[a[i]]]=1;
            }
        }
        tp();
        iqiq++; 
        cout<<"Case #"<<iqiq<<": ";
        if(oh_no[dad[1]]) cout<<"UNBOUNDED\n";
        else cout<<c[dad[1]]<<"\n";
        q_g_w_d();
    }
    return 0;
}

~都写这么多了，就给个赞吧~。