AtCoder Regular Contest 106 解题报告

arc106_b Values

AtCoder Regular Contest 106 的第二题,签到。

题目链接:B – Values

题意翻译

  • 给定一张 \( n \) 个点 \( m \) 条边的无向图;
  • 每次可以让一条边连接的两个顶点的权值一个增加 \( 1 \),另一个减少 \( 1 \);
  • 给定每个点的初始权值 \( a _ i \) 和最终权值 \( b _ i \),要你判定是否可行,输出判断结果即可;
  • 数据范围:\( 1 \leq n \leq 2 \times 10 ^ 5 \) ,\( 0 \leq m \leq 2 \times 10 ^ 5 \),\( – 10 ^ 9 \leq a _ i , b _ i \leq 10 ^ 9 \),无自环重边。

题解

显然一个连通块内的任意两点都可以互相修改权值,所以我们只需要判断每一个连通块内的 \( \sum a _ i \) 与 \( \sum b _ i \) 是否相等即可。

#include <bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++)
static char buf[100000], *p1 = buf, *p2 = buf;
inline int read(void)
{
    reg bool f = false;
    reg char ch = getchar();
    reg int res = 0;
    while (!isdigit(ch))
        f |= (ch == '-'), ch = getchar();
    while (isdigit(ch))
        res = 10 * res + ch - '0', ch = getchar();
    return f ? -res : res;
}

const int MAXN = 2e5 + 5;
const int MAXM = 2e5 + 5;

namespace UnionFind
{
    int fa[MAXN];
    ll sum[MAXN];
    inline void Init(reg int n, reg int a[], reg int b[])
    {
        for (reg int i = 1; i <= n; ++i)
        {
            fa[i] = i;
            sum[i] = a[i] - b[i];
        }
        return;
    }
    inline int find(reg int x)
    {
        if (x == fa[x])
            return x;
        else
            return fa[x] = find(fa[x]);
    }
    inline void merge(reg int a, reg int b)
    {
        reg int ra = find(a), rb = find(b);
        if (ra != rb)
        {
            fa[rb] = ra;
            sum[ra] += sum[rb];
        }
        return;
    }
    inline bool search(reg int a, reg int b)
    {
        return find(a) == find(b);
    }
} // namespace UnionFind

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

int main(void)
{
    n = read(), m = read();
    for (reg int i = 1; i <= n; ++i)
        a[i] = read();
    for (reg int i = 1; i <= n; ++i)
        b[i] = read();
    UnionFind::Init(n, a, b);
    for (reg int i = 1; i <= m; ++i)
    {
        static int c, d;
        c = read(), d = read();
        UnionFind::merge(c, d);
    }
    reg bool flag = true;
    for (reg int i = 1; i <= n && flag; ++i)
    {
        reg int r = UnionFind::find(i);
        if (UnionFind::sum[r])
            flag = false;
    }
    puts(flag ? "Yes" : "No");
    return 0;
}
Pages: 1 2 3 4 5 6 7 8