[POI2011] SMI-Garbage 题解

题目链接

显然，对于初始颜色与目标颜色不同的边，我们需要走过奇数次；对于初始颜色与目标颜色相同的边，我们需要走过偶数次。

对于只有偶数边的情况，这种情况下不走就行；对于只有奇数边；可以理解为每条边只能经过一次，就是欧拉路径问题，并且考虑这题的特殊性质，如果一个图是由若干个简单环构成的连通图，那么显然每个点度数为偶数，毕竟环都是进一次出一次。所以在判断方面，只需判断偶数边即可。

那么我们考虑将两种情况合起来，可以发现，如果只有奇数边情况无解，那么加几个偶数边也无济于事，所以对于偶数边，就不用加了，只加奇数边，那么一定会形成若干连通块，分别对每个连通块进行考虑即可。

对于一个连通块，先求出其欧拉路径，然后用类似 tarjan 的方法，设置一个栈，一旦遇到与当前栈的元素重复就加进新的答案。具体看代码。

有一说一，原来用的 \(vector+map\) 做，超时，但是用邻接表做则可以AC，果然常数还是太大了。

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

typedef long long LL;
#define PII pair<int,int>
inline LL read() {
	LL sum=0,flag=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
	while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
	return sum*flag;
}

const int N=1e5+10,M=2e6+10;
int n,m,ans_cnt;
int fa[N],vis[N];
int del[N],deg[N];
vector<int> id[N],ans[N];
stack<int> st;
int f[M],tot=1,h[N],to[M],nxt[M];

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

int find(int x) {
	if(x==fa[x]) return x;
	else return fa[x]=find(fa[x]);
}

void merge(int x,int y) {
	int fx=find(x),fy=find(y);
	if(fx!=fy) fa[fx]=fy;
}

void dfs(int nd) {
	for(int i=h[nd];i;i=nxt[i]) {
		if(f[i]) continue;
		int x=to[i];
		f[i]=f[i^1]=1;
		h[nd]=nxt[i];
		dfs(x);
	}
	st.push(nd);
}

int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) {
		int a=read(),b=read(),s=read(),t=read();
		if(s!=t) {
			add(a,b); add(b,a);
			deg[a]++; deg[b]++;
			merge(a,b);
		}
	}
	for(int i=1;i<=n;i++) {
		id[find(i)].push_back(i);
	}
	for(int i=1;i<=n;i++) {
		if(fa[i]==i) {
			int cnt=0,sz=id[i].size();
			for(int x:id[i]) {
				if(deg[x]%2==0) cnt++;
			}
			if(cnt==sz) {
				dfs(id[i][0]);
				stack<int> stk;
				while(st.size()) {
					int x=st.top(); st.pop();
					if(vis[x]) {
						++ans_cnt; int y=0;
						do {
							y=stk.top();
							ans[ans_cnt].push_back(y);
							vis[y]=0; stk.pop();							
						}while(y!=x);
					}
					stk.push(x); vis[x]=1;
				}
			}
			else {
				cout<<"NIE"; return 0;
			}
		}
	}
	cout<<ans_cnt<<endl;
	for(int i=1;i<=ans_cnt;i++) {
		cout<<ans[i].size()<<" ";
		for(int x:ans[i]) cout<<x<<" ";
		cout<<ans[i][0]<<"\n";
	}
	return 0;
}