自动搬运

查看原文

来自洛谷，原作者为

	Esucu 真实实力：AT perf 842，CF < 1200

搬运于2025-08-24 23:10:03，当前版本为作者最后更新于2024-12-04 16:13:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Subtask1

考虑随便搜出一棵生成树，然后删掉剩余 $m-n+1$ 条边，从起点开始，每次从当前点暴力跑 dfs 走到下一条要删的边的端点（这样可以保证走的点之前没有被删过），然后删掉这条边就行。

总共经过 $m-n+1$ 轮，每轮最多走 $m$ 条边，因此边数最多为 $m(m-n+1)$，复杂度是 $O(m^2)$。

Subtask2

把暴力跑 dfs 换成暴力跑树边就能把复杂度降至 $O(nm)$。

Subtask3

依然沿用 Subtask1 的做法，边数是 $n$ 条，复杂度是 $O(n+m)$。

Subtask4

考虑贴近正解。

如果没有“删除一条边后就不能再走”的限制这题是简单的，直接把每条边都遍历一遍就行了。

添加这个要求后，我们就要考虑如何不重复地经过每条边。

考虑到“不重复”，可以想到欧拉回路（欧拉路径也是一样）。对于原图是欧拉图的情况，总步数可以不超过 $m$。因为我们可以跑一遍欧拉回路，每遍历到一条边，若它是树边则不删去，否则删去。欧拉回路是为了保证每条边可以不重不漏地走一次。

否则的话原图存在奇度点，考虑把这些奇度点“去掉”。事实上，我们跑出来的路径不一定要是严格的欧拉回路。因为一条边实际上可以经过多次，我们只需要再最后删除就行了。我们可以给每条路径新增一个“通过次数”。我们可以给奇度点两两分组，给每组组内两个点间的任意简单路径上的每条边的“通过次数”都加一，可以看做将该路径复制一遍（以下简称加边），使得原图转化为欧拉图。

这样最多有 $\frac{n}{2}$ 组，每组最多加 $n-1$ 条边，总边数控制在 $m+\frac{n(n-1)}{2}$ 内。

然而如果暴力跑 dfs 时间复杂度是 $O(nm)$ 的，依然可以通过把暴力跑 dfs 换成暴力跑树边，复杂度做到 $O(n^2+m)$。

Subtask5

你已经非常接近正解了！

考虑优化一下分组，使得新加入的边尽量少。

可以这样加边：搜一遍生成树，在回溯时若该点为奇度点，则将该点与其父亲节点加边。

可以证明这样加完边后原图一定是欧拉图。

简单证明：用这样的操作，因为回溯时才加边保证了非根节点一定可以变成偶度点，而每一次加边，节点度数和的奇偶性不变，一开始是偶数个，加完边后也是偶数个，又因为没有其他偶度点了，所以根节点也是偶度点。

这样，就在每条树边最多复制一次的情况下让每个点的度数均变成了偶数。

理一遍思路：直接跑生成树，给树边打标记，奇度点加边，跑欧拉回路输出路径。

总边数 $m+n-1$ 条，复杂度 $O(n+m)$。

std：

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
const int M=5e5+5;
int n,m,s,u,v,cnt=1,cntans,to[N+M<<1],id[N+M<<1],nxt[N+M<<1],h[N],d[N],ans[N+M];
bool tag[M],vis[N+M<<1];
void save(int u,int v,int w){
	to[++cnt]=v;
	id[cnt]=w;
	nxt[cnt]=h[u];
	h[u]=cnt;
	d[u]++;
}
void dfs(int u){
	vis[u]=1;
	for(int i=h[u];i;i=nxt[i]){
		if(vis[to[i]]||i>(m<<1|1)) continue;
		tag[id[i]]=1;
		dfs(to[i]);
		if(d[to[i]]&1){
			save(u,to[i],id[i]);
			save(to[i],u,id[i]);
		}
	}
}
void dfs2(int u){
	for(int &i=h[u];i;i=nxt[i]){
		if(vis[i]) continue;
		vis[i]=vis[i^1]=1;
		int k=id[i];
		dfs2(to[i]);
		ans[++cntans]=k;
	}
}
int main(){
	scanf("%d%d%*d%d",&n,&m,&s);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&u,&v);
		save(u,v,i);
		save(v,u,i);
	}
	dfs(s);
	memset(vis,0,sizeof(vis));
	dfs2(s);
	printf("%d\n",cntans);
	for(int i=cntans;i>=1;i--) printf("%d %d\n",ans[i],(int)tag[ans[i]]);
	return 0;
}