边
题目描述
本题中所有的图都指的是无重边无自环的无向图。
定义正则图为每个点度数都相等的图，\(k\) 正则图为每个点度数都为 \(k\) 的图，偶正则图为每个点度数都为偶的图。
有一张偶正则图，构造删边方案使之变成 \(2\) 正则图（就是若干个环）。
\(n,m\leq 10^5\)
解法
首先有一个经典问题，如果是有向图要求环的话，我们把每个点拆成入点和出点，跑二分图匹配就可以得到答案。
但是这道题给的是无向图，那么给无向图的每条边定向就可以用有向图的方法了。注意到每个点的度数都是偶数且相等这个关键条件，可以跑原图的欧拉回路来定向，这样每个点就有 \(k\) 个入边和 \(k\) 个出边了。
但是我们要证明转化过来的有向图也一定能求出解才算严谨。根据 \(\tt Hall\) 定理：如果 \(X\) 部的任意若干个点至少和 \(Y\) 部等量的点相邻，那么这个图存在完备匹配。考虑 \(X\) 部的 \(x\) 个点，至少向 \(Y\) 部连了 \(kx\) 个边，如果对应的点数小于 \(x\) 说明存在度数大于 \(k\)，矛盾，故一定会有解。
最后再说一些关于欧拉回路的细节，因为这题的欧拉回路是要把每个边访问一遍，正常的欧拉回路是访问每个点，所以在 \(\tt dfs\) 的时候要 充分的扩展，一条路走到黑是不行的，所以有一个地方要 \(\tt break\)
二分图匹配用 \(\tt dinic\)，总所周知复杂度是 \(O(m\sqrt m)\) 的。
#include <cstdio>
#include <vector>
#include <queue>
#include <map>
using namespace std;
const int M = 200005;
const int inf = 0x3f3f3f3f;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,tot,s,t,f[M],cur[M],dis[M];
vector<int> g[M];map<int,int> mp[M];
struct edge
{
int v,c,next;
}e[10*M];
void add(int u,int v,int c)
{
e[++tot]=edge{v,c,f[u]},f[u]=tot;
e[++tot]=edge{u,0,f[v]},f[v]=tot;
}
void euler(int u)
{
for(int i=0;i<g[u].size();i++)
{
int v=g[u][i];
if(!mp[u][v])
{
mp[u][v]=mp[v][u]=1;
add(u+n,v,1);//出点和入点连边
euler(v);
//break;
}
}
}
int bfs()
{
queue<int> q;
for(int i=0;i<=t;i++) dis[i]=0;
q.push(s);dis[s]=1;
while(!q.empty())
{
int u=q.front();q.pop();
if(u==t) return 1;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v;
if(!dis[v] && e[i].c>0)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return 0;
}
int dfs(int u,int ept)
{
if(u==t) return ept;
int flow=0,tmp=0;
for(int &i=cur[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==dis[u]+1 && e[i].c>0)
{
tmp=dfs(v,min(ept,e[i].c));
if(!tmp) continue;
ept-=tmp;
flow+=tmp;
e[i].c-=tmp;
e[i^1].c+=tmp;
if(!ept) break;
}
}
return flow;
}
signed main()
{
freopen("edg.in","r",stdin);
freopen("edg.out","w",stdout);
n=read();m=read();
s=0;t=2*n+1;tot=1;
for(int i=1;i<=m;i++)
{
int u=read(),v=read();
g[u].push_back(v);
g[v].push_back(u);
}
euler(1);
for(int i=1;i<=n;i++)
add(s,i+n,1),add(i,t,1);
while(bfs())
{
for(int i=0;i<=t;i++) cur[i]=f[i];
k+=dfs(s,inf);
}
for(int i=2;i<=tot;i++)
{
int u=e[i].v,v=e[i^1].v;//考虑的是反向边
if(u<=2*n && u>n && v<=n && v>=1 && e[i].c)
mp[u-n][v]=mp[v][u-n]=0;
}
printf("%d\n",m-k);
for(int i=1;i<=n;i++)
for(int j=0;j<g[i].size();j++)
if(i<g[i][j] && mp[i][g[i][j]])
printf("%d %d\n",i,g[i][j]);
}