CF723E One-Way Reform 欧拉序
传送门
答案上界为该无向图中的偶点数量,考虑构造方案达到这个上界
建一个虚点S向所有奇点连边,这样奇点都变成了偶点,而奇点的个数一定是偶数,故S也是个偶点
于是新图存在欧拉回路,根据这个对边进行定向,则原图中所有偶点入度等于出度,达到上界
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
| #include <bits/stdc++.h> #define MAXN 205 using namespace std; int G[MAXN][MAXN]; inline int read() { int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9') { x=(x*10)+(ch-'0'); ch=getchar(); } return x*f; } int deg[MAXN]; inline void AddEdge(int u,int v){ G[u][v]=G[v][u]=1; deg[u]++,deg[v]++; } inline void DelEdge(int u,int v){ G[u][v]=G[v][u]=0; deg[u]--,deg[v]--; } int n,m; void dfs(int u){ for (register int i=1;i<=n+1;++i){ if (G[u][i]){ if (i!=n+1&&u!=n+1){ printf("%d %d\n",u,i); } DelEdge(i,u); dfs(i); } } } int main(){ int t=read(); while (t--){ n=read(),m=read(); for (register int i=1;i<=m;++i){ int u=read(),v=read(); AddEdge(u,v); } int ans=0; for (register int i=1;i<=n;++i){ if (deg[i]&1){ AddEdge(i,n+1); } else { ans++; } } printf("%d\n",ans); for (register int i=1;i<=n;++i) dfs(i);;; } }
|