luogu(spj有锅,最多90')

loj

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

#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\n",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\n",an[ta][0]); --ta; } return 0; }

转载于:https://www.cnblogs.com/smyjr/p/11145433.html

原文链接：https://blog.csdn.net/weixin_30342827/article/details/95863163

本站声明:网站内容来源于网络,如有侵权,请联系我们,我们将及时处理。