【Codeforces 527E】Data Center Drama | Mrsrz's blog

欧拉回路，构造。

题目大意：

给定一张无向连通图，要求加入最少的边，并给无向图定向，使得每个点的入度和出度都是偶数。输出方案。

题解：

每个点的度数为偶数，则每个连通块都为欧拉图。

考虑原来的无向图，可能存在度数为奇数的点，这样的点一定有偶数个。我们将其两个两个配对并连边，可以使所有点的度数都是偶数。

然后求欧拉回路。对于一个欧拉回路，我们将路径上的点依次排列以后，按照一条边从左到右，一条边从右到左的顺序连边，即可使除了起点以外的所有点都满足偶数的度数条件。起点如果存在度数为奇数的情况，可以连一条自环解决。

由于原图是无向连通图，所以这样的答案一定是最小的。

Code：

#include<cstdio>
#include<vector>
using namespace std;
const int N=4e5+5;
struct edge{
    int to,nxt,id;
}e[N<<1];
int cnt=1,head[N],n,m,deg[N],top;
bool vis[N];
int sta[N];
vector<pair<int,int> >vc;
bool vs[N];
inline void addedge(int u,int v,int w){
    e[++cnt]=(edge){v,head[u],w},head[u]=cnt;
    e[++cnt]=(edge){u,head[v],w},head[v]=cnt;
}
void dfs(int now){
    for(int&i=head[now];i;i=e[i].nxt)
    if(!vis[e[i].id]){
        vis[e[i].id]=1;
        --deg[e[i].to],--deg[e[i^1].to];
        dfs(e[i].to);
    }
    sta[++top]=now;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        int u,v;
        scanf("%d%d",&u,&v);
        ++deg[u],++deg[v];
        addedge(u,v,i);
    }
    int lst=0;
    for(int i=1;i<=n;++i)if(deg[i]&1){
        if(!lst)lst=i;else addedge(lst,i,++m),lst=0,++deg[lst],++deg[i];
    }
    for(int i=1;i<=n;++i)if(deg[i]){
        top=0;
        dfs(i);
        if(top&1^1)sta[++top]=sta[1];
        for(int i=1;i<top;++i)
        if(i&1)vc.emplace_back(sta[i],sta[i+1]);else vc.emplace_back(sta[i+1],sta[i]);
    }
    printf("%u\n",vc.size());
    for(auto i:vc)
    printf("%d %d\n",i.first,i.second);
    return 0;
}