题目大意

题目链接
你有一个无向连通图，边的总数为偶数。
设图中有 $k$ 个奇点（度数为奇数的点），你需要把它们配成 $\frac{k}{2}$ 个点对（显然 k 被 $2$ 整除）。对于每个点对 $(u,v)$，你需要用一条长度为偶数（假设每条边长度为 $1$ ）的路径将 $u$ 和 $v$ 连接。每条路径允许经过重复的点，但不允许经过重复的边。这 $\frac{k}{2}$ 条路径之间也不能有重复的边。
$n,m \leq 250000$
可惜是个权限题 题目只能去 bzoj 交

题解

首先如果丢掉每条路径都是偶数的限制 就是建一个虚点 每个奇点和这个虚点连边 求个欧拉回路就好了。
类似于 CF547D 我们想到了二分图（二分图从一个方向出去会从另一个方向回来 这样转回来后一定是偶数）所以建模考虑用二分图：每个点拆成 $u_1$ 和 $u_2$。那么对于原来的边 $(u,v)$ 现在有两种连边策略：$(u_1,v_2)$ 或 $(u_2,v_1)$。这里注意所有虚点的连边一定都连向拆点后的第一个点$u_1$。如果确定出了一个欧拉图，就可以从虚点开始找欧拉回路 输出就可以了。
所以现在我们要确定每个边怎么连 使得这个图是一个欧拉图，也就是所有的点度数均为奇数。
我们发现我们只需要考虑一边就可以了：因为原来每个点都是偶数 那么新的图中拆出的两个点的和是偶数 所以只需要一个是偶数就可以了。我们研究左边的这一侧。对于这种问题一种方法是先随便找出一个生成树。非树边任意定向，树边从叶子开始每次将这个点和父亲的边更改使得满足这个点是偶数即可。正确性显然。

#include<bits/stdc++.h>

#define fi first
#define se second
#define U unsigned
#define P std::pair<int,int>
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl

const int MAXN = 1e6 + 5;

struct Edge{
    int to,w,nxt; // id
}e[MAXN<<1];
int head[MAXN],cnt = 1;
bool used[MAXN<<1];
int n,m;

inline void add(int u,int v,int w){
//    printf("%d %d %d\n",u,v,w);
    e[++cnt] = (Edge){v,w,head[u]};head[u] = cnt;
    e[++cnt] = (Edge){u,w,head[v]};head[v] = cnt;
}
std::vector<int> S,tmp;
inline void dfs(int v){
    for(int &i = head[v];i;i = e[i].nxt){
        if(used[e[i].w]) continue;
        used[e[i].w] = 1;
        int t = i;dfs(e[i].to);
        S.pb(e[t].w);
    }
}

std::vector<P> G[MAXN];
int f[MAXN];
int du[MAXN],du2[MAXN];
inline int find(int x){return x == f[x] ? x : f[x] = find(f[x]);}
inline bool merge(int x,int y){x = find(x);y = find(y);if(x == y) return 0;f[x] = y;return 1;}

inline void dfs2(int v,int fa=0,int fae=0){
    FOR(i,0,(int)G[v].size()-1){
        P x = G[v][i];
        if(x.fi == fa) continue;
        dfs2(x.fi,v,x.se);
    }
    if(fa){
        if(du[v] & 1) add(v,fa+n,fae),du[v]++,du[fa+n]++;
        else add(v+n,fa,fae),du[v+n]++,du[fa]++;
    }
}

int main(){
    scanf("%d%d",&n,&m);FOR(i,1,n) f[i] = i;int tt = 0;
    FOR(i,1,m){
        int u,v;scanf("%d%d",&u,&v);
        ++du2[u];++du2[v];
        if(merge(u,v)){++tt;
            G[u].pb(MP(v,i));G[v].pb(MP(u,i));
        } 
        else{
            add(u,n+v,i);du[u]++;du[n+v]++;
        }
    }
    FOR(i,1,n) if(du2[i]&1) du[i]++;
    dfs2(1);
    FOR(i,1,n) if(du2[i]&1) add(n*2+1,i,m+i);
    dfs(2*n+1);std::reverse(all(S));
//    FOR(i,1,2*n) DEBUG(du[i]);
    int las = 0;
//    for(auto x:S) printf("%d ",x);
//    exit(0);
    FOR(i,0,(int)S.size()-1){
        int x = S[i];
        if(x > m){
            if(!las) las = x;
            else{
                printf("%d %d %d\n",las-m,x-m,(int)tmp.size());
                FOR(j,0,(int)tmp.size()-1) printf("%d ",tmp[j]);puts("");las = 0;tmp.clear();    
            }
        }
        else tmp.pb(x);
    }
    return 0;
}
/*
6 8
1 2
2 3
3 4
4 5
5 6
6 1
1 4
2 5
*/

总结

1. 二分图有很好的对称性质 对路径的奇偶性也有很好的性质
2. 想要让一个图所有的点都是偶数 可以搞出一个生成树来调整