bzoj3724: PA2014Final Krolestwo

构造 图论

不会欧拉回路怎么办啊【跑

考虑建一个额外的点，所有奇数点连过去跑一个欧拉回路，这样可以构造出一组路径，但不能保证长度为偶数。

考虑进行这样一种操作，将相邻的边缩成$m/2$对，即将两边的点不经过中点直接相连。如果这样操作可行，显然所有点的奇偶性不变，且在新图上跑欧拉回路可以得到偶数长度的路径。

下面证明这样的操作可行：设$dfs(nd)$表示将$nd$子树中所有树边和非树边合并，（如果必须）剩下$nd$与其父亲的连边。$dfs(nd)$先对于所有的儿子调用$dfs(to)$，然后将剩余的边（树边或非树边）两两合并，如果剩下一条，将其和$nd$的父亲合并；否则剩下$nd$与父亲的边。当这个过程执行到根时，所有的边就合并好了（因为只有可能剩下一条或全部合并成功，而边数为偶数，因此必然全部合并成功）。

于是在新图上跑欧拉回路即可。

写起来像吃了屎一样。。。不过思路很优雅，算法即证明【是不是可以给MO当毒瘤题啊2333

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500005;
inline int read()
{
    int a = 0, c;
    do c = getchar(); while (!isdigit(c));
    while (isdigit(c)) {
        a = a*10+c-'0';
        c = getchar();
    }
    return a;
}
int cnt = 0;
struct node {
    int to, next, x, y;
} edge[MAXN*2], e[MAXN*3];
int head[MAXN], top = -1;
int h[MAXN], tot = -1;
inline void push(int i, int j)
{ edge[++top] = (node) {j, head[i], 0, 0}, head[i] = top; }
inline void push2(int i, int j, int x, int y)
{
    e[++tot] = (node) {j, h[i], x, y}, h[i] = tot;
    e[++tot] = (node) {i, h[j], y, x}, h[j] = tot;
}
int vis[MAXN], v[MAXN], d[MAXN], n, m;
void dfs(int nd, int f, int t)
{
    int last_to = 0, last_e = 0;
    v[nd] = 1;
    for (register int i = head[nd]; i != -1; i = edge[i].next) {
        int to = edge[i].to;
        if (to == f) continue;
        if (!v[to]) dfs(to, nd, (i>>1)+1);
        if (!vis[(i>>1)+1]) {
            if (last_to) push2(last_to, to, last_e, (i>>1)+1), vis[(i>>1)+1] = vis[last_e] = 1, last_to = 0;
            else last_to = to, last_e = (i>>1)+1;
        }
    }
        if (last_to) {
        push2(last_to, f, last_e, t);
        vis[last_e] = vis[t] = 1;
    }
}
int ans[MAXN*2], ans_top = 0;
int cur[MAXN];
void dfs_find(int nd)
{
    for (int &i = cur[nd]; i != -1; i = e[i].next) {
        int to = e[i].to;
        if (vis[i>>1]) continue;
        vis[i>>1] = 1;
        int tmp = i;
        dfs_find(to);
        if (to == n+1) ans[++ans_top] = -nd;
        else if (nd == n+1) ans[++ans_top] = -to;
        else ans[++ans_top] = e[tmp].y, ans[++ans_top] = e[tmp].x;
    }
}
int main()
{
    memset(head, -1, sizeof head);
    memset(h, -1, sizeof h);
    n = read(), m = read();
    for (register int i = 1; i <= m; i++) {
        int u = read(), v = read();
        d[u]++, d[v]++;
        push(u, v), push(v, u);
    }
    dfs(1, 0, 0);
    for (register int i = 1; i <= n; i++)
        if (d[i]&1)
            push2(i, n+1, -1, -1);
    memcpy(cur, h, sizeof h);
    memset(vis, 0, sizeof vis);
    dfs_find(n+1);
    int last = 1, cc = 0;
    for (register int i = 2; i <= ans_top; i++) {
        if (ans[i] < 0) {
            if (last == 0) last = i;
            else {
                printf("%d %d %d\n", -ans[last], -ans[i], i-last-1), cc += i-last-1;
                for (register int j = last+1; j < i; j++)
                    printf("%d ", ans[j]);
                puts("");
                last = 0;
            }
        }
    }
    return 0;
}