luogu(spj有锅,最多90')
首先可以把初始状态和最终状态不一样的边看成黑边,其他的看成白边,那么就是要把所有黑边变白.那个把边取反看似很烦,但实际上通过手玩可以发现,我们只要能选出若干边不相交的黑环,并且所有黑边都被选上,那么就可以得到解了.因为如果选出若干边相交的环,那么取反后等价于选了若干边不相交的环(可以随便画一下).找环的话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;
}