第一次打线上赛，1456分来着，感觉自己模拟题做的不怎么样，总是想复杂，而且写代码慢的要死，这套题说实话还算简单，但只A了两道，其他的题都很基础，这题欧拉通路我刚好不会，所以写一下。
题意：
n个城市之间m条双向道路，现在把双向道路变成单向，求让出入度相同的城市最多的路线图。
要点：
这题就是个欧拉通路问题，因为要把双向变成单向，所以原本的出度如果是奇数，说明这个顶点的入度和出度不相等，原本是偶数的直接就是相等的，所以最大城市数就是n-出度奇数个数。现在问题是怎么输出最后的路线图，我们引入一个新顶点，将所有出度为奇数的点与新顶点连接，这样图中所有点的出入度都相等。这里说明一下出度为奇数的点一定是偶数个，因为一条边对应两个点，这里多一个那边就少一个。这样对整个图进行dfs输出欧拉回路即可。
#include#include #include using namespace std;set edge[210];//用set方便之后删除边int t, n, m;void dfs(int i){ if (edge[i].empty())//如果当前顶点没有出去的边就返回 return; int x = *edge[i].begin(); edge[i].erase(x);//将经过的边消除 edge[x].erase(i); if (i != n + 1 && x != n + 1)//新加入的点不参与输出 printf("%d %d\n", i, x); dfs(x);}int main(){ int i, j; scanf("%d", &t); while (t--) { scanf("%d%d", &n, &m); for (i = 0; i < 210; i++) edge[i].clear(); int u, v; for (i = 1; i <= m; i++) { scanf("%d%d", &u, &v); edge[u].insert(v); edge[v].insert(u); } for(i=1;i<=n;i++) if (edge[i].size() & 1) { edge[i].insert(n + 1); edge[n + 1].insert(i); } printf("%d\n", n-edge[n + 1].size()); for (i = 1; i <= n; i++) { while (!edge[i].empty()) { dfs(i); } } } return 0;}