BZOJ2278 [Poi2011]Garbage[欧拉回路求环]

首先研究环上性质，发现如果状态不变的边就不需要动了，每次改的环上边肯定都是起末状态不同的边且仅改一次，因为如果有一条边在多个环上，相当于没有改，无视这条边之后，这几个环显然可以并成一个大环。所以，我们只关注起末状态不同的边。

然后，这些边形成一张图。对于每个连通块，如果有解的话，应当是一堆边不相交的简单环通过点互相连接的。这样一张图等价于一个欧拉回路，所以只要判每个连通块是不是欧拉回路（偶数度）即可。

然后是求解，目标就是把每个连通块所有的简单环都拎出来。回顾上述欧拉回路判断，实际上正是因为若干简单环构成的图可以一笔画。。所以仿照一笔画过程（也就是栈中记录的访问点顺序），再开一个栈，不断压栈，当遇到一个先前已经压到栈的点的时候说明形成了一个简单环，一直弹栈直到先前点为止，这时弹出元素就构成了一个环。。这样所有环就出来了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #define mst(x) memset(x,0,sizeof x)

 #define dbg(x) cerr << #x << " = " << x <<endl

 #define dbg2(x,y) cerr<< #x <<" = "<< x <<"  "<< #y <<" = "<< y <<endl

 using namespace std;

 typedef long long ll;

 typedef double db;

 typedef pair<int,int> pii;

 template<typename T>inline T _min(T A,T B){return A<B?A:B;}

 template<typename T>inline T _max(T A,T B){return A>B?A:B;}

 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,):;}

 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,):;}

 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;}

 template<typename T>inline T read(T&x){

     x=;int f=;char c;while(!isdigit(c=getchar()))if(c=='-')f=;

     while(isdigit(c))x=x*+(c&),c=getchar();return f?x=-x:x;

 }

 const int N=1e5+,M=1e6+;

 struct thxorz{

     int head[N],to[M<<],nxt[M<<],tot;

     thxorz(){tot=;}

     inline void add(int x,int y){

         to[++tot]=y,nxt[tot]=head[x],head[x]=tot;

         to[++tot]=x,nxt[tot]=head[y],head[y]=tot;

     }

 }G;

 int deg[N],stk[M],vis[M<<],bin[M],bcnt,top,st[N],tp,instk[N];

 int n,m,cnt;

 #define y G.to[j]

 void dfs(int x){//dbg(x);

     for(register int&j=G.head[x];j;j=G.nxt[j])if(!vis[j])vis[j]=vis[j^]=,bin[++bcnt]=j,dfs(y);

     stk[++top]=x;

 }

 #undef y

 vector<int> ans[M];

 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout);

     read(n),read(m);

     for(register int i=,x,y,z,w;i<=m;++i){

         read(x),read(y),read(z),read(w);

         if(z^w)G.add(x,y),++deg[x],++deg[y];

     }

     for(register int i=;i<=n;++i)if(deg[i]&){puts("NIE");return ;}

     for(register int i=;i<=n;++i)if(G.head[i]){

         dfs(i);tp=;//dbg(i);

         while(bcnt)vis[bin[bcnt]]=vis[bin[bcnt]^]=,--bcnt;

         while(top){

             int x=stk[top--];//dbg(x);

             if(!instk[x])instk[x]=,st[++tp]=x;

             else{

                 ans[++cnt].push_back(x);

                 do instk[st[tp]]=,ans[cnt].push_back(st[tp--]);while(st[tp]^x);

                 ans[cnt].push_back(x);

             }

         }

     }

     printf("%d\n",cnt);

     for(register int i=;i<=cnt;++i,puts("")){

         printf("%d ",ans[i].size()-);

         for(register int j=;j<ans[i].size();++j)printf("%d ",ans[i][j]);

     }

     return ;

 }

总结：这题启示我们在有关简单环的问题中，除了点双、边双等等转化策略以外，在涉及环的方面也可以采用欧拉路来考虑。总之，解决环相关的问题大概就是点双、边双、欧拉路以及栈的思想、dfs以及二分图染色等方法。

巴特西

BZOJ2278 [Poi2011]Garbage[欧拉回路求环]

最新文章

热门文章