luogu P3520 [POI2011]SMI-Garbage

luogu(spj有锅,最多90')

loj

首先可以把初始状态和最终状态不一样的边看成黑边,其他的看成白边,那么就是要把所有黑边变白.那个把边取反看似很烦,但实际上通过手玩可以发现,我们只要能选出若干边不相交的黑环,并且所有黑边都被选上,那么就可以得到解了.因为如果选出若干边相交的环,那么取反后等价于选了若干边不相交的环(可以随便画一下).找环的话dfs然后开栈记录路径上节点就可以做了,具体细节见代码

upd:其实就是求欧拉回路

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL long long
#define db double

using namespace std;
const int N=1e5+10,M=1e6+10;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
    return x*w;
}
int to[M<<1],nt[M<<1],w[M<<1],hd[N],tot=1;
void add(int x,int y,int z)
{
    ++tot,to[tot]=y,nt[tot]=hd[x],w[tot]=z,hd[x]=tot;
    ++tot,to[tot]=x,nt[tot]=hd[y],w[tot]=z,hd[y]=tot;
}
int n,m,st[N][2],tp,ta;
bool v[N];
vector<int> an[M];
void dfs(int x,int ffa)
{
    while(hd[x]&&!w[hd[x]]) hd[x]=nt[hd[x]];
    for(int i=hd[x];i;i=nt[i])
        if(i!=ffa&&w[i])
        {
            int y=to[i];
            st[++tp][0]=y,st[tp][1]=i;
            if(!v[y])
            {
                v[y]=1,dfs(y,i^1),v[y]=0;
                if(tp&&st[tp-1][0]!=x) break;
                if(!tp&&st[tp][0]!=x) break;
                if(!tp) continue;
                --tp;
            }
            else
            {
                ++ta;
                do
                {
                    an[ta].push_back(st[tp][0]);
                    v[st[tp][0]]=0;
                    w[st[tp][1]]=w[st[tp][1]^1]=0;
                    --tp;
                }
                while(st[tp][0]!=y);
                v[y]=1;
                return;
            }
        }
}

int main()
{
    n=rd(),m=rd();
    for(int i=1;i<=m;++i)
    {
        int x=rd(),y=rd(),z=rd()^rd();
        add(x,y,z);
    }
    for(int x=1;x<=n;++x)
    {
        st[0][0]=x,tp=0,v[x]=1;
        dfs(x,0);
        v[x]=0;
    }
    for(int i=1;i<=m;++i)
        if(w[i<<1]||w[i<<1|1]) {puts("NIE");return 0;}
    printf("%d
",ta);
    while(ta)
    {
        int nn=an[ta].size();
        printf("%d ",nn);
        for(int i=0;i<nn;++i) printf("%d ",an[ta][i]);
        printf("%d
",an[ta][0]);
        --ta;
    }
    return 0;
}