CodeForces - 453C Little Pony and Summer Sun Celebration
程序员文章站
2022-06-27 17:12:16
博主的 BiBi 时间小马宝莉。。。在博主的少年时代是博主即使不做作业也要看的动画片。然而,还是没有读对题。Description图可能有几个连通块。不能从每个连通块重新开始。Solution其实思路很新奇。把图化成树。如果儿子的奇偶性不对,就走到父亲再回来。父亲同理。对于根节点没有爸爸,可以通过最后是否停在根节点来改变奇偶性。关于根节点的选取,我们尽量选择 aaa 值为 111 的。因为可能只有一个 111,但是不与外界相连的情况。Code#include
博主的 BiBi 时间
小马宝莉。。。在博主的少年时代是博主即使不做作业也要看的动画片。
然而,还是没有读对题。
Description
- 图可能有几个连通块。
- 不能从每个连通块重新开始。
Solution
其实思路很新奇。
把图化成树。如果儿子的奇偶性不对,就走到父亲再回来。父亲同理。
对于根节点没有爸爸,可以通过最后是否停在根节点来改变奇偶性。
关于根节点的选取,我们尽量选择 值为 的。因为可能只有一个 ,但是不与外界相连的情况。
Code
#include <cstdio>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n, m, a[N], s[N];
bool vis[N];
vector <int> e[N], ans;
int read() {
int x = 0, f = 1; char s;
while((s = getchar()) > '9' || s < '0') if(s == '-') f = -1;
while(s >= '0' && s <= '9') x = (x << 1) + (x << 3) + (s ^ 48), s = getchar();
return x * f;
}
void dfs(const int u, const int root, const int fa) {
ans.push_back(u); s[u] = 1; vis[u] = 1;
for(int i = 0; i < e[u].size(); ++ i) {
int v = e[u][i];
if(vis[v]) continue;
dfs(v, root, u);
}
if(u == root && s[u] != a[u]) {
ans.pop_back(); s[u] ^= 1;
return;
}
if(u == root) return;
if(s[u] != a[u]) {
ans.push_back(fa); ans.push_back(u);
s[u] ^= 1; s[fa] ^= 1;
}
ans.push_back(fa); s[fa] ^= 1;
}
bool ok() {
for(int i = 1; i <= n; ++ i) if(s[i] != a[i]) return 0;
return 1;
}
int main() {
int u, v;
n = read(), m = read();
for(int i = 1; i <= m; ++ i) {
u = read(), v = read();
e[u].push_back(v); e[v].push_back(u);
}
for(int i = 1; i <= n; ++ i) a[i] = read();
int start = 1;
for(int i = 1; i <= n; ++ i)
if(a[i] == 1) start = i;
dfs(start, start, 0);
if(! ok()) return puts("-1"), 0;
printf("%d\n", ans.size());
for(int i = 0; i < ans.size(); ++ i) printf("%d ", ans[i]);
return 0;
}
本文地址:https://blog.csdn.net/LBCLZMB/article/details/107622438
下一篇: 中小企业数据备份解决方案