题目 题意：将无向图转为有向图，并且出度等于入度的点的数目最大。输出具体方案。保证无重边无自环
Solution
根据之前欧拉回路的知识：对于有向图，只有所有点的出度和入度都相等的图才有欧拉回路。 这正和题目要求的出度和入度都相等的点尽量多类似，于是我们可以把这张图的所有奇点两两连一条边，使得连完边之后的图存在欧拉回路。 直接跑欧拉回路，根据经过的边定向即可。 可以发现这种方法达到了答案的上界，所以是正确的
Code
#include<bits/stdc++.h>
using namespace std
;
const int N
=202;
struct node
{
int to
,ne
;
}e
[N
*N
];
int h
[N
],tot
,cnt
,i
,n
,m
,T
,deg
[N
],x
,y
;
set
<pair
<int,int> >S
;
bool vis
[N
];
inline char gc(){
static char buf
[100000],*p1
=buf
,*p2
=buf
;
return p1
==p2
&&(p2
=(p1
=buf
)+fread(buf
,1,100000,stdin),p1
==p2
)?EOF:*p1
++;
}
inline int rd(){
int x
=0,fl
=1;char ch
=gc();
for (;ch
<48||ch
>57;ch
=gc())if(ch
=='-')fl
=-1;
for (;48<=ch
&&ch
<=57;ch
=gc())x
=(x
<<3)+(x
<<1)+(ch
^48);
return x
*fl
;
}
inline void wri(int a
){if(a
<0)a
=-a
,putchar('-');if(a
>=10)wri(a
/10);putchar(a
%10|48);}
inline void wln(int a
){wri(a
);puts("");}
void add(int x
,int y
){
e
[++tot
]=(node
){y
,h
[x
]};
h
[x
]=tot
;
}
void dfs(int u
){
vis
[u
]=1;
for (;h
[u
];){
int v
=e
[h
[u
]].to
;h
[u
]=e
[h
[u
]].ne
;
if (S
.count(make_pair(v
,u
))) continue;
S
.insert(make_pair(u
,v
));
if (u
&& v
) wri(u
),putchar(' '),wln(v
);
dfs(v
);
}
}
int main(){
for (T
=rd();T
--;){
n
=rd();m
=rd();
tot
=0;memset(h
,0,(n
+1)<<2);
cnt
=0;memset(deg
,0,(n
+1)<<2);
memset(vis
,0,n
+1);
S
.clear();
for (i
=1;i
<=m
;i
++) x
=rd(),y
=rd(),add(x
,y
),add(y
,x
),deg
[x
]++,deg
[y
]++;
for (i
=1;i
<=n
;i
++)
if (deg
[i
]&1) add(0,i
),add(i
,0),cnt
++;
wln(n
-cnt
);
for (i
=1;i
<=n
;i
++)
if (!vis
[i
]) dfs(i
);
}
}
ps：这程序还是用vector存方便
