CF242D题解

传送门：https://codeforces.com/problemset/problem/242/D

对于一个点，显然一旦达到额定值后，其他任何操作都无法使他减小，于是我们得出一个贪心性质，当且仅当一个点不合法时，才取增加他的值。同理，我们可以证明，问题必定有解，因为若一个点被选择，必定是因为其曾不合法，选择后使其\(+1\)合法，而若最后一个点不合法，其必定是未选择的，选择其则能合法。过程可以用队列维护。时间复杂度\(O(n)\)。

#include <bits/stdc++.h>

using namespace std;

inline int read() {
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9') if (c == '-') flag = true;
    int res = c - '0';
    while ((c = getchar()) >= '0' && c <= '9') res = (res << 3) + (res << 1) + c - '0';
    return flag ? -res : res;
}

const int N = 1e5 + 10;

int head[N], cnt, a[N], b[N], step[N];

struct Edge {
    int v, next;
} e[N * 2];

void add(int u, int v) {
    e[cnt].v = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}

int main() {
    memset(head, -1, sizeof head);
    int n = read(), m = read();
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read();
        add(u, v);
        add(v, u);
    }
    for (int i = 1; i <= n; ++i) a[i] = read();
    int ans = 0;
    queue<int> q;
    for (int i = 1; i <= n; ++i) if (!a[i]) q.push(i);
    while (!q.empty()) {
        if (b[q.front()] != a[q.front()]) {
            q.pop();
            continue;
        }
        step[++ans] = q.front();
        ++b[q.front()];
        q.pop();
        for (int i = head[step[ans]]; ~i; i = e[i].next) {
            if (++b[e[i].v] == a[e[i].v]) q.push(e[i].v);
        }
    }
    printf("%d\n", ans);
    for (int i = 1; i <= ans; ++i) {
        printf("%d ", step[i]);
    }
    return 0;
}