P8405 Naboj 题解

Demeanor_Roy · 2022-11-11 14:51:02 · 题解

• 原题链接

• 小清新构造题。

• 一开始拿到题可能比较没有头绪，这时有一个小技巧：从特殊情况入手，先看看什么时候无解。

• 我们将一条导线看作一条有向边，边的方向是从离电子远的点到离电子近的点。这时如果你随便在草稿纸上手玩几个样例就会发现：似乎图有环就无解！

• 让我们来严格证明一下这个结论：考虑一个环上最后一个被充电的点，无论我们给它充正电还是负电，它连接的两条边由于需求冲突，都会有一条边在充电后不满足要求。而环上的边只有环上的点能影响，这时我们就推出只要给环上的点充电，就一定不满足要求。而如果不给环上的任意一个点充电，当然也是不合法的，所以结论得证。

• 那此时我们就可以先把环判掉，接下来就是在 DAG 上解决问题。

• 由于是 DAG ，不难想到先将整张图按拓扑序排好，我们按拓扑序顺序考虑每个点，发现与这个点相连的边分为两类：一类是连向之前已经考虑过的点，一类是连向还未考虑的点，前一类边要求这个点充正电，后一类则相反。由于后一类边还有挽救的余地，那对当前点来说，我们当然是先满足前者。

• 于是我们就得到一个策略，按拓扑序给每一个点充正电。

• 让我们证明这个策略的正确性：对于每一条边，一定是它通向的点后考虑，而它通向的点一定会满足它的需求，正确性得证。

• 注意事项：

1. 判环可以在拓扑排序中判定，不需要专门判断。

2. 可能有人会疑惑我有环就无解这个结论只证明了充分性，可实际上后面构造方案时其实就相当于顺便证明了必要性。

• 于是这道题就结束了，下附代码：

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

const int N=2e5+10,M=5e5+10;
int n,m,din[N],q[N];
int h[N],e[M],ne[M],idx;
vector<int> ans;
inline void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
inline bool topsort()
{
    int head=1,tail=0;
    for(int i=1;i<=n;i++)   if(!din[i]) q[++tail]=i;
    while(head<=tail)
    {
        int now=q[head++];
        for(int i=h[now];~i;i=ne[i])
        {
            din[e[i]]--;
            if(!din[e[i]])
            {
                q[++tail]=e[i];
                ans.push_back(e[i]);            
            }
        }
    }
    return tail==n;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        add(v,u);din[u]++;
    }
    if(!topsort())  puts("-1");
    else    
    {
        printf("%d\n",(int)ans.size());
        for(auto now:ans)   printf("%d 1\n",now);
    }
    return 0;
}

• 完结撒花~