今晚题解

题意概述

给定一张 \(n\) 个点 \(m\) 条边的有向图 \(G\) 。

有 \(n\) 个硬币。初始时有的正面朝上，有的反面朝上。每次你可以手动翻转一枚。

如果在 \(G\) 中有边 \(a\rightarrow b\) ，那么当第 \(a\) 枚硬币（被手动或自动）翻转后，第 \(b\) 枚也会被自动翻转。注意：它可以传递下去。

但如果你手动翻转某一枚后会触发无限次操作，那波特就直接炸了，你不能使其触发这种情况。

给定初始每个硬币的状态，求至少操作多少次后能使所有硬币都正面朝上。

无解输出 -1 。

思路概述

这道题其实是一个拓扑排序的思维题，先反向拓扑排序判断是不是无解，反向拓扑之后，如果剩下的点有反着的硬币，则说明无解（我考场上就想到这里了），因为如果有这样的反着的硬币，那一定不能成。然后正着拓扑，同时记下到这个点的翻转次数，如果当前点翻转次数是奇数且是正面朝上或者翻转次数是偶数且是负面朝上，那就该翻转这个点，一直这样跑完就行了。

code

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

const int N=5e5+10;
int n,m,a[N];
int to[N],nxt[N],h[N],tot;
int deg[N],Deg[N],v[N],cnt[N];
int res;
vector<int> ver[N];
int X[N],Y[N];

void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=h[x];
    h[x]=tot;
    deg[y]++;
}

void topsort_()
{
    queue<int> q;
    for(int i=1;i<=n;i++)if(!deg[i])q.push(i),v[i]=true;
    while(q.size())
    {
        int x=q.front();
        q.pop();
        for(int i=h[x];i;i=nxt[i])
        {
            int y=to[i];
            if(--deg[y]==0)q.push(y),v[y]=true;
        }
    }
}

bool judge()
{
    for(int i=1;i<=n;i++)
    {
        if(!v[i]&&!a[i])return false;
    }
    return true;
}

bool need(int x)
{
    if(!a[x]&&!(cnt[x]%2))return true;
    if(a[x]&&(cnt[x]%2))return true;
    return false;
}

void topsort()
{
    queue<int> q;
    for(int i=1;i<=n;i++)
    {
        if(!Deg[i])
        {
            q.push(i);
        }
    }
    while(q.size())
    {
        int x=q.front();
        q.pop();
		if(need(x))cnt[x]++,res++;
        for(int y:ver[x])
        {
            cnt[y]+=cnt[x];
            if(--Deg[y]==0) q.push(y);
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(y,x);
		X[i]=x;
		Y[i]=y;
    }
    topsort_();
    if(!judge())
    {
        cout<<-1;
        return 0;
    }
	for(int i=1;i<=m;i++)
	{
		int x=X[i];
		int y=Y[i];
		if(!v[x]||!v[y])continue;
		ver[x].push_back(y);
		Deg[y]++;
	}
    topsort();
    cout<<res;
    return 0;
}