传送门:https://codeforces.com/problemset/problem/549/B
和CF242C思路完全相同,对于一个点,显然一旦达到额定值后,其他任何操作都无法使他减小,于是我们得出一个贪心性质,当且仅当一个点不合法时,才取增加他的值。同理,我们可以证明,问题必定有解,因为若一个点被选择,必定是因为其曾不合法,选择后使其
合法,而若最后一个点不合法,其必定是未选择的,选择其则能合法。过程可以用队列维护。时间复杂度\(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;
}vector<int> e[101];
char s[101];
int a[101];int main() {int n = read();for (int i = 1; i <= n; ++i) {scanf("%s", s + 1);for (int j = 1; j <= n; ++j) if (s[j] == '1') e[i].push_back(j);}vector<int> ans;queue<int> q;for (int i = 1; i <= n; ++i) {a[i] = read();if (!a[i]) q.push(i);}while (!q.empty()) {int x = q.front();q.pop();ans.push_back(x);for (int y: e[x]) {--a[y];if (!a[y]) q.push(y);}}sort(ans.begin(), ans.end());printf("%zu\n", ans.size());for (int k: ans) printf("%d ", k);return 0;
}