标题

t162 · 2022-10-07 14:45:16 · 题解

先考虑最大的点，这个点一定能够说服所有的村庄。而别的村庄为了能够说服这个最大的村庄，必须要先通过说服别的村庄来达到目的。

先把这个最大的村庄删掉，剩下的图就会分成若干个连通块。显然如果一个村庄能够说服图中所有的村庄，那么必然能先说服自己属于的连通块的村庄。并且能够说服这个最大的村庄，就能够说服整张图中的村庄。而如果一个连通块中的所有村庄的人数之和都没有这个最大的村庄多，那么这个连通块中的村庄就不可能说服所有村庄。把这样的连通块删掉，剩下的直接递归下去就行了。

具体实现的时候，为了方便，可以使用并查集重新建树。时间复杂度 \mathcal O(n\log n)。

// Author: e3c8f1a924   Time: 2022年10月07日 星期五 14时18分51秒
#include<cstdio>
#include<algorithm>
#include<vector>
typedef long long ll;
int f[200005], _[200005], n, vis[200005], m, s[200005], ans[200005];
ll S[200005];
std::vector<int> e[200005], son[200005];
int find(int x) { return f[x] == x ? x : (f[x] = find(f[x])); }
void dfs(int u) {
    S[u] = s[u];
    for (int v : son[u]) dfs(v), S[u] += S[v];
}
void solve(int u) {
    ans[u] = 1;
    for (int v : son[u]) {
        if (S[v] >= s[u]) solve(v);
    }
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) scanf("%d", s + i);
    for (int i = 1; i <= m; i++) {
        int u, v; scanf("%d%d", &u, &v);
        e[u].push_back(v), e[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) f[i] = i;
    for (int i = 1; i <= n; i++) _[i] = i;
    std::sort(_ + 1, _ + n + 1, [=](int x, int y) { return s[x] < s[y]; });
    for (int i = 1; i <= n; i++) {      // 重新建树
        for (int j : e[_[i]]) {
            if (!vis[j]) continue;
            if (find(j) == _[i]) continue;
            son[_[i]].push_back(find(j));
            f[find(j)] = _[i];
        }
        vis[_[i]] = 1;
    }
    int tot = 0;
    for (int i = 1; i <= n; i++) if (f[i] == i) tot++;
    if (tot > 1) {
        for (int i = 0; i < n; i++) putchar('0');
        return puts(""), 0;
    }
    dfs(_[n]), solve(_[n]);
    for (int i = 1; i <= n; i++) printf("%d", ans[i]);
    return puts(""), 0;
}