PA2014 Final, BZOJ3724 Krolestwo

题目大意

你有一个$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;
}