首页 > 代码库 > codeforces 723E - One-Way Reform
codeforces 723E - One-Way Reform
题目链接:http://codeforces.com/problemset/problem/723/E
-----------------------------------------------------------------------
首先可以想一想给定一个图 如果不要求输出方案的话答案是多少
由于初始度数为奇数的点无论怎样 最后也不可能修改成入度 = 出度的
因此答案一定不超过初始度数为偶数的点的个数
再考虑这些初始度数为奇数的点 由于是无向图 这样的点的个数显然是偶数个的
我们如果对这些点每两个分为一组 组内连一条无向边
显然对于每个联通块 都可以找到一条欧拉回路 而欧拉回路中所有点的入度 = 出度
也就是说这样修改后所有点都是合法的了 如果再把之前添加了的边去掉
那么初始度数为偶数的点不受影响 初始度数为奇数的点全部变为不合法点
因此对于任意一个图 都可以构造出一个答案等于初始度数为偶数的点的个数的方案
于是这题接下来只需要会用求欧拉回路的方法就可以解决了
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 210, E = N * N << 1; 4 int firste[N], nexte[E], v[E], d[N]; 5 bool used[N], mp[N][N], color[E]; 6 int e; 7 void build(int x, int y, int z = 1) 8 { 9 nexte[++e] = firste[x];10 firste[x] = e;11 v[e] = y;12 color[e] = 0;13 if(z)14 ++d[x];15 }16 int sta[N], route[E];17 int t, n, m, top, len;18 void dfs(int u)19 {20 used[u] = 1;21 for(int p = firste[u]; p; p = nexte[p])22 if(!color[p])23 {24 color[p] = color[p ^ 1] = 1;25 dfs(v[p]);26 }27 route[len++] = u;28 }29 int main()30 {31 scanf("%d", &t);32 while(t--)33 {34 memset(firste, 0, sizeof firste);35 memset(d, 0, sizeof d);36 memset(used, 0, sizeof used);37 memset(mp, 0, sizeof mp);38 e = 1;39 scanf("%d%d", &n, &m);40 int x, y;41 for(int i = 1; i <= m; ++i)42 {43 scanf("%d%d", &x, &y);44 build(x, y);45 build(y, x);46 mp[x][y] = mp[y][x] = 1;47 }48 top = 0;49 int ans = n;50 for(int i = 1; i <= n; ++i)51 if(d[i] & 1)52 {53 --ans;54 if(top & 1)55 {56 build(i, sta[top - 1], 0);57 build(sta[top - 1], i, 0);58 }59 sta[top++] = i;60 }61 len = 0;62 for(int i = 1; i <= n; ++i)63 if(!used[i])64 dfs(i);65 printf("%d\n", ans);66 for(int i = 0; i < len; ++i)67 if(mp[route[i]][route[(i + 1) % len]])68 {69 mp[route[i]][route[(i + 1) % len]] = mp[route[(i + 1) % len]][route[i]] = 0;70 printf("%d %d\n", route[i], route[(i + 1) % len]);71 }72 }73 return 0;74 }
codeforces 723E - One-Way Reform
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。