DDOSvoid's Blog

CF 1537F Figure Fixing

发表于 分类于
本文字数： 1.7k 阅读时长 ≈ 2 分钟

题目描述

http://codeforces.com/problemset/problem/1537/F

简要题意：给定一张 $n$ 个点 $m$ 条边的无向连通图，每个点有一个权值 $a_i$，每次操作可以使一条边相连的两个点同时增加任意一个整数值，求是否能使所有点的权值都为 $0$​

$n,m\le 2\times 10^5$

Solution

首先注意到我们的操作不能改变权值总和的奇偶性，所以如果和为奇数则一定不行

然后我们注意到我们可以将距离为奇数的两个点同时增加相同的数值，距离为偶数的点一个增加另一个减少相同的数值

这启示我们考虑二分图的性质，首先我们将这张图分成两种情况考虑，二分图和不是二分图

如果该图是二分图，那么我们只需要看一下两边点的总和是否相等，相等则一定有解，不相等则一定无解

如果改图不是二分图，那么就一定存在奇环，对于一个存在奇环的图，任意两个点都存在一条长度为奇数的路径，所以一定有解

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
#include <iostream>
#include <vector>
#include <algorithm>
#define maxn 200010
#define ll long long
#define INF 1000000000
using namespace std;

int n, m;
int a[maxn], b[maxn];

struct Edge {
    int to, next;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
    e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}

int vis[maxn];
bool dfs(int u, int d) {
    vis[u] = d;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (vis[v] == d) return 0;
        if (vis[v] == -1 && !dfs(v, d ^ 1)) return 0;
    }
    return 1; 
}

void work() {
    cin >> n >> m;
    fill(head + 1, head + n + 1, -1); c1 = 0;
    fill(vis + 1, vis + n + 1, -1); ll sum = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i], sum += a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i], sum -= b[i];
    for (int i = 1; i <= m; ++i) {
        int x, y; cin >> x >> y;
        add_edge(x, y); add_edge(y, x); 
    }
    if (sum & 1) return cout << "NO" << "\n", void();
    if (!dfs(1, 0)) return cout << "YES" << "\n", void();
    sum = 0; 
    for (int i = 1; i <= n; ++i)
        if (vis[i]) sum += a[i] - b[i];
        else sum -= a[i] - b[i];
    cout << (sum == 0 ? "YES" : "NO") << "\n";
}

int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int T; cin >> T;
    while (T--) work(); 
    return 0; 
}