crazy_cloud's Blog
0%

PA2014 Final, BZOJ3724 Krolestwo

Posted on Edited on In

题目大意

你有一个 \(n\) 个点 \(m\) 条边的无向连通图，边的总数为偶数。

设图中有 \(k\) 个奇点（度数为奇数的点），你需要把它们配成 \(\frac k2\) 个点对（显然 \(k\) 被 \(2\) 整除）。对于每个点对 \((u,v)\)，你需要用一条长度为偶数（假设每条边长度为 \(1\)）的路径将 \(u\) 和 \(v\) 连接。

每条路径允许经过重复的点，但不允许经过重复的边。这 \(\frac k2\) 条路径之间也不能有重复的边。

无解输出 NIE。

\(2\leq n,m\leq 2.5\times10^5\)

题目分析

首先一看度数奇偶性以及不能经过重复的边但是可以经过重复的点，就能猜到是欧拉路径相关。

那么怎么把问题转化成欧拉回路呢？考虑加入一个特殊点，其向每一个奇点都有连边，然后可以发现题目要求的加上这些边就是欧拉回路了。

可是直接这样做可能会有问题：题目要求的是长度为偶数的路径。我们这样搞不一定能弄到偶数长度的。

怎么办呢？考虑奇偶染色的思路。我们将每一个点 \(x\) 拆成 \(u_x\) 和 \(v_x\) 两个点，如果我们能够保证欧拉路径在从特殊点进入 \(u\) 之后是交替经过两种点最后从 \(u\) 点回到特殊点，那么问题就解决了。

考虑让特殊点只和奇点 \(x\) 的 \(u_x\) 连边。然后对于原来的边 \((x,y)\)，我们需要决定到底是选择连 \((u_x,v_y)\) 还是 \((v_x,u_y)\)，这怎么办呢？

对于一个奇点，它的 \(u_x\) 已经和特殊点有连边，为了使其有欧拉回路我们还需要给它连上奇数条路径，一个偶点的 \(u_x\) 则只需要偶数条。（显然考虑了 \(u\) 点满足就不需要考虑 \(v\) 点）

问题可以抽象成给一个无向连通图定向，使得某些点出度为奇数，其余为偶数。我们可以随便找一棵 DFS 树，对于非树边随意定向，然后从叶子开始向上考虑，通过调整连接父亲的边的方向来满足条件。至于根节点，简单的验算即可以证明由于原图边总数是偶数的，只要非根节点满足了条件根节点一定可以满足条件。

然后跑一遍 Hierholzer’s algorithm 找欧拉回路就好了。时间复杂度 \(O(n+m)\)。

至于什么无解，当然是不存在的啦！

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>

using namespace std;

inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)) f=ch=='-'?-1:f,ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*f;
}

int buf[30];

inline void write(int x)
{
	if (x<0) putchar('-'),x=-x;
	for (;x;x/=10) buf[++buf[0]]=x%10;
	if (!buf[0]) buf[++buf[0]]=0;
	for (;buf[0];putchar('0'+buf[buf[0]--]));
}

const int N=250005;
const int M=250005;
const int V=N<<1;
const int E=M+N<<1;

struct edge
{
	int x,y;
}edg[M];

int tov[E],nxt[E],euler_path[E];
int matchpath[M];
bool is_fwd[M];
bool used[E];
bool vis[V];
int last[V];
int deg[N];
int n,m,tot,el,len;

inline void insert(int x,int y){tov[++tot]=y,nxt[tot]=last[x],last[x]=tot;}
inline void addedge(int x,int y){insert(x,y),insert(y,x);}

void clearedge(){memset(last,0,sizeof last),memset(nxt,0,sizeof nxt),memset(tov,0,sizeof tov),tot=0;}

void determine(int x,int e=0)
{
	bool out_degree=0;
	vis[x]=1;
	for (int i=last[x],y;i;i=nxt[i])
		if (e!=i+1>>1)
		{
			if (vis[y=tov[i]]) is_fwd[i+1>>1]=0;
			else determine(y,i+1>>1);
			out_degree^=is_fwd[i+1>>1]^(edg[i+1>>1].y==x);
		}
	if (e) if (out_degree^(deg[x]&1)) out_degree^=1,is_fwd[e]=edg[e].x==x;
	else is_fwd[e]=edg[e].y==x;
}

void Hierholzer(int x,int e=0)
{
	for (;last[x]&&used[last[x]];last[x]=nxt[last[x]]);
	if (last[x])
	{
		int i=last[x],y=tov[i];
		used[i]=used[((i-1)^1)+1]=1,Hierholzer(y,i);
	}
	if (e) euler_path[++el]=e;
}

void process()
{
	for (int i=el,e,st=0,en=0;i>=1;--i)
	{
		e=euler_path[i];
		if (tov[e])
			if (!st) st=en=tov[e],len=0;
			else en=tov[e],matchpath[++len]=e+1>>1;
		else
		{
			write(st+1>>1),putchar(' '),write(en+1>>1),putchar(' '),write(len),putchar('\n');
			for (int j=1;j<=len;++j) write(matchpath[j]),putchar(j<len?' ':'\n');
			st=0;
		}
	}
}

int main()
{
	freopen("kro.in","r",stdin),freopen("kro.out","w",stdout);
	n=read(),m=read();
	for (int i=1,x,y;i<=m;++i) ++deg[edg[i].x=x=read()],++deg[edg[i].y=y=read()],addedge(x,y);
	determine(1),clearedge();
	for (int i=1;i<=m;++i)
		if (is_fwd[i]) addedge(edg[i].x*2-1,edg[i].y*2);
		else addedge(edg[i].x*2,edg[i].y*2-1);
	for (int i=1;i<=n;++i) if (deg[i]&1) addedge(0,i*2-1);
	Hierholzer(0),process();
	fclose(stdin),fclose(stdout);
	return 0;
}