题解：P3520 [POI2011] SMI-Garbage

· · 题解

2024/11/26 更新

POI2011 SMI-Garbage

一篇题解记录这道写了三天的题。

容易发现，题目需要找到几个环使得一些边恰好经过一次。忽略掉不用改变颜色的边，题目就转化为找到覆盖剩下所有边的欧拉回路，所以无解情况也就是有点度数是奇数的情况。

但是欧拉回路中会有重复点，这里我们可以用栈维护当前经过的点，如果遍历到的点在栈中出现过，就弹栈记录答案，然后继续从该点跑欧拉回路。

Code

#include<bits/stdc++.h>
using namespace std;
struct Edge{
    int u,v,nxt;
}a[2000005];
int n,m,ct=1,deg[100005],head[100005],now[100005],ans;
bool vis[200005],vv[2000005];//vis记录是否在栈中
stack<int>s;
vector<int>res[1000005];
void add(int u,int v){
    a[++ct]={u,v,head[u]};
    head[u]=ct;
}
void dfs(int u){
    s.push(u);--deg[u];//到达一点度数减一，统计度数方便统计是否所有边都遍历到
    if(vis[u]){
        ++ans;s.pop();res[ans].push_back(u);
        while(!s.empty()){
            if(s.top()==u)break;
            vis[s.top()]=false;
            res[ans].push_back(s.top());
            s.pop();
        }res[ans].push_back(u);
    }
    vis[u]=true;
    for(int i=now[u];i;i=now[u]){
        now[u]=a[i].nxt;
        if(vv[i]||vv[i^1])continue;
        vv[i^1]=vv[i]=true;--deg[u];//遍历下一个点时度数减一
        dfs(a[i].v);break;
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1,u,v,s,t;i<=m;i++){
        cin>>u>>v>>s>>t;
        if(s==t)continue;//不用改的边忽略
        add(u,v),add(v,u);
        deg[u]++,deg[v]++;
    }
    for(int i=1;i<=n;i++)if(deg[i]&1)cout<<"NIE",exit(0);//判无解
    for(int i=1;i<=n;i++)now[i]=head[i];
    for(int i=n;i>=1;i--)
        while(deg[i])deg[i]++,dfs(i);
    cout<<ans<<'\n';
    for(int i=1;i<=ans;i++){
        cout<<(int)res[i].size()-1<<' ';
        for(auto v:res[i])cout<<v<<' ';
        cout<<'\n';
    }
}