P8405 题解

snowane · 2026-08-03 16:19:47 · 题解

题意

有几个小球，每个球都有两种状态：负电荷会把电子送给和它连有电线的所有球，正电荷会把和它连有电线的球的电子吸过来，如果一个球充了多次电，效果以最后一个为准。

思路

首先观察题目给到的限制充电次数，k 就是 n 的最大值，所以范围较广，不是那么局限。

如果我们随意乱充电，充电时交换顺序效果不同，那么可能出现后效性，然后整个都乱套了。这个时候我们会发现，如果你按照题目当中给的边按照拓扑序去充电，那么我们就可以只去充一种电荷，这里写的正电荷写法。

如果出现了环，那么就会互相产生依赖关系，无法达成目标。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

int cnt=0,n,m;
int d[200005],ans[200005];
vector<int>e[200005];
queue<int>q;

void topsort()
{
    for(int i=1;i<=n;i++)
    {
        if(d[i]==0)
        {
            q.push(i);
        }
    }
    while(q.size()!=0)
    {
        int t=q.front();
        q.pop();
        cnt++;
        ans[cnt]=t;
        for(int i=0;i<e[t].size();i++)
        {
            d[e[t][i]]--;
            if(d[e[t][i]]==0)
            {
                q.push(e[t][i]);
            }
        }
    }
}

signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v;
        cin>>u>>v;
        e[v].push_back(u);//注意此处存边是反图
        d[u]++;
    }
    topsort();
    if(cnt!=n)//构成环
    {
        cout<<-1;
        return 0;
    }
    cout<<n<<endl;
    for(int i=1;i<=cnt;i++)
    {
        cout<<ans[i]<<" "<<1<<endl;//所有都充正电荷
    }
    return 0;
}