CF1494F Delete The Edges 题解

Description

给定一张 $n$ 个点、$m$ 条边的图，你可以从图上任意一点出发，目标是删去所有的边，当一条边被删去后你不能再走此边。

初始模式下，一条边在你走过后会立即被删去。

你可以在任意一点切换模式（或全程不换），换完模式后走过的第偶数条便会被删去，且不可重新换回初始模式。

求一组方案。

Solution

观察样例可得切换模式后走的图为一个菊花图，下面浅浅分析一下。

假设只有一条边，则折返走一遍便能删完。

若为两条边 $(i,j),(j,k)$，发现只能 $j\to i\to j\to k\to j$ 将其删完。

依此类推，删边必须像 $i\to j\to i$ 折返地删。

所以我们可以枚举菊花图的中心，构造出走一条终点为菊花图中心的欧拉路径，然后切换模式的方案。

关键在于如何求出这条欧拉路径。

首先将所有和中心相连的奇点（度数为奇）和中心连的这条边删去，这样这个点就会变为偶点（度数为偶），方便后续操作。

然后得出当前图中奇点个数 $cnt$，和中心度数是否为 $0$，记为 $f$。

若 $f=true$：

• $cnt>2$，无法构出欧拉路径，非法。

• $cnt=2$ 且中心不为奇点，终点不为中心，非法。

• $cnt=2$ 且外围图不连通（除去度数为 $0$ 的点，这些点虽然不连通，但切换模式后都会连通），非法。

• $cnt=2$ 且外围连通，即我们已经构造出了合法方案。

若 $f=false$：

• $cnt\ge 2$，还要连一条边到中心，然而再加边就不是欧拉路径了，非法。

剩下还剩当前路径有中心但外围不连通、当前路径不含中心两种情况，发现 $cnt=0$ 使得我们可以在加一条删去的边到欧拉路径上，那我们就枚举这条边。

首先当前外围图（此时是除去度数为 $0$ 的点但此点不为中心）连通块个数要小于等于 $2$，因为加一条边只能让两个连通块连通。

然后分别将这两连通块染色，遍历删去的边，若边的两顶点颜色不同，则加上这条边，发现这种合法方案的起点就是这两顶点中不是中心的那个点。

发现一定存在这条先前被删去的边，即我们一定能找到合法方案。

然后我们按输出要求输出方案即可，首先遍历欧拉路径，再切换模式，然后折返删菊花图。

代码细节很多，理清思路再写。

时间复杂度 $O(n(n+m))$

Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int tot,head[3030];
int in[3030],du[3030],col[3030];
bool vis[3030],viss[3030],pit[3030];
vector<int> path;
struct edge{
int to,next,id;
}e[6060];
void add(int x,int y,int z){
e[++tot]=edge{y,head[x],z};
head[x]=tot;
}
void dfs(int x,int v=0){
viss[x]=1;
col[x]=v;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to,w=e[i].id;
if(viss[y]||vis[w]) continue;
dfs(y,v);
}
}
void get(int x){
bool f=0;
int ss,ww;
for(int i=head[x];i;i=e[i].next){
int y=e[i].to,w=e[i].id;
if(!vis[w]){
vis[w]=1;
get(y);
path.push_back(x);
}
}
}
bool solve(int st){
for(int i=1;i<=n;i++) du[i]=in[i],viss[i]=0,pit[i]=0,col[i]=0;
for(int i=1;i<=m;i++) vis[i]=0;
bool f=0;
int ts=0,ttot=0;  //ts为方案起点、ttot为切换模式后删的边数
for(int i=head[st];i;i=e[i].next){
int y=e[i].to,w=e[i].id;
if(du[y]%2){  //删去中心与偶点相连的边
pit[y]=1,du[y]--,du[st]--,vis[w]=1,ttot++;
}else f=1;  //中心是否在当前欧拉路径上
}
int cnt=0,fl=0;
for(int i=1;i<=n;i++){
if(du[i]%2) cnt++;  //奇点数量
if(du[i]%2&&i!=st) fl=i;  //得出合法欧拉路径的起点
}
if(f){
if(fl==0) fl=st;  //欧拉回路则任选起点
if(cnt>2) return 0;
if(cnt==2&&du[st]%2==0) return 0;
if(cnt==2){
dfs(st);
for(int i=1;i<=n;i++){  //判断外围连通性
if(du[i]==0) continue;
if(!viss[i]) return 0;
}
ts=fl;
}

}else{
if(cnt>=2) return 0;
}
if(cnt==0){
dfs(st);  //染第一个连通块
bool ff=0;
for(int i=1;i<=n;i++){
if(du[i]==0) continue;
if(!viss[i]){
if(ff) return 0;  //有至少三个连通块
dfs(i,1);
ff=1;
}
}
if(ff){
for(int i=head[st];i;i=e[i].next){
int y=e[i].to,w=e[i].id;
if(pit[y]&&col[y]){  //是之前删去的奇点且与中心不在同一连通块上
pit[y]=0,vis[w]=0,ttot--;
ts=y,du[y]++,du[st]++;
break;
}
}
}else{  //只有一个连通块即为欧拉回路
ts=st;
}
}
cout<<m+ttot+2<<'\n';  //m条边要删完则有m次操作，ttot条边被操作2次，加上起点和切换模式的2次操作
get(ts);  //遍历欧拉路径
for(int i=path.size()-1;i>=0;i--) cout<<path[i]<<" ";
cout<<st<<" ";
cout<<-1<<" ";
for(int i=head[st];i;i=e[i].next){
int y=e[i].to,w=e[i].id;
if(pit[y]){
cout<<y<<" "<<st<<" ";  //折返删菊花图
}
}
return 1;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(nullptr);
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
in[x]++,in[y]++;
add(x,y,i),add(y,x,i);
}
for(int i=1;i<=n;i++){
if(solve(i)){
return 0;
}
}
cout<<"0"<<'\n';  //无解
return 0;
}

原文地址：https://blog.csdn.net/m0_66438282/article/details/142470054

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！