P3520 [POI2011]SMI-Garbage 题解
big_turkey · · 题解
2024/11/29 更新
题解又被人hack了，来补。
把原来存欧拉回路的空间上限增大了。
这里感谢 @chenxi2009 指出错误。
2021/10/18 更新
题解被人hack了，一年后过来补。
这里感谢 @fzj2007 提供的hack数据。
下面代码已通过LOJ的强数据和hack数据。
下面部分更新的地方都用粗体表示
题目分析
总共有m条边，走过一条边就是修改该边权值。
每次要求走过一个简单环上的边，即从某个点开始走过该点存在的联通图（原图可能不联通），初始权值与最终权值相等的边走偶数次，不相等的走奇数次。
为什么用欧拉回路？
-
欧拉回路的定义：存在一条从某个点开始，恰好不重不漏经过每条边一次（点可重复），最终回到该点。
-
欧拉图的定义：存在欧拉回路的图。
-
欧拉图的判定：每个点的度数都为偶数。
通过以上定义和判定，可以考虑权值不相等的边通过找欧拉回路的方法来。
权值相等的边，因为每次都必须走偶数次，相当于拆成了两条边，这样实际上就使得改边对连接的两点度数加了 +2，根据欧拉回路的定义，删去这条边即对两点度数 -2，还使得图成为欧拉图了（只用走剩下的边一次），就可以直接找欧拉回路了。
原代码没有处理不经过重复边或起点以外结点的环，即每次只能走以起点开始的环
这样的话，就可以再开一个栈专门来存当前的欧拉回路，如果当前的点已经在栈中，说明已经形成一个环，将该环储存答案并弹出。
代码细节处理
我原来的代码是用栈模拟 dfs 的搜索和回溯过程。
每次取栈顶元素，遍历其没有遍历过的边，将出点存入栈中。
遍历没有遍历过的边后要将链头都要指向下一条未遍历的边，以保证时间复杂度正确。
如果没有可遍历的出边，那么就应该回溯，将该点弹出并存入答案栈中，此时答案栈存入的即是以
代码
以下代码省去模板和一些简单的宏。
应该没问题吧
const ll maxn=1e5+5,maxm=1e6+5;
ll n,m,cnt=1,head[maxn];
ll deg[maxn];
ll tot;
vector<ll> ans[maxm];
ll stk[maxm],tp;
ll stkans[maxm],tpans;//存欧拉回路的答案栈
bool instk[maxm]；//标记是否在答案栈中
bool vis[maxm];
struct edge{
ll to,next,vis;
}e[maxm<<1];
void add(ll x,ll y){
e[++cnt]=(edge){y,head[x],0};
head[x]=cnt;
deg[x]++;
}
#define failed return puts("NIE"),0
void euler(ll s){
stk[tp=1]=s;
for(ll x,i;tp;){
x=stk[tp],i=head[x];
while(i&&e[i].vis)
head[x]=i=e[i].next;
if(i){
stk[++tp]=e[i].to;
e[i].vis=e[i^1].vis=true;
head[x]=e[i].next;//链头指向下一条边
}
else{
tp--;
vis[x]=true;
if(instk[x]){
ans[++tot].push_back(x);
while(tpans&&stkans[tpans]!=x)
ans[tot].push_back(stkans[tpans]),
instk[stkans[tpans--]]=false;
ans[tot].push_back(x);
}
else instk[stkans[++tpans]=x]=true;
}
}
}
void output(){
printf("%lld\n",tot);
FOR(i,1,tot){
printf("%lld\n",ans[i].size()-1);
for(auto x:ans[i]) printf("%lld ",x);
puts("");
}
}
int main(){
n=read(),m=read();
for(ll x,y,o,p;m;m--){
x=read(),y=read(),o=read(),p=read();
if(o^p) add(x,y),add(y,x);
}
FOR(i,1,n) if(deg[i]&1) failed;
FOR(i,1,n) if(!vis[i]) euler(i);
output();
return 0;
}