博弈!!!!!!!
给出一棵树 每次 A 可以选择一个点染 A，B 可以选择一个点把它和与它相邻的点染 B
B 可以在任何时候去掉一些边，但总数不超过一个定值 染过的点不能选择，染色标记可以覆盖
若最后所有点都染 B 色，B 赢，否则 A 赢 .
让我们种下一棵‘树’，可以推知：
（1）若原树不存在完美匹配，A 一定赢
A 每次操作可以强迫 B 和他一起染掉一个匹配
最后肯定会剩下孤立点，A 再选这个点就是 A 色了。
（2）如果 K = 0 , N≥ 3 若原树不存在完美匹配，由结论 1，A 赢
若存在，A 可以第一步强迫 B 破坏掉完美匹配的性质，依然 A 赢
所以贪心看下树有没有完美匹配就好了
代码如下：
#include <cstdio> #include <algorithm> #include <vector> #define FOR(i, l, r) for(int i = l; i <= r; ++i) #define mp(x, y) make_pair(x, y) using namespace std; typedef long long ll; const int N = 200010; const ll inf = 1e15; struct edge{int u, v, lim;} e[N]; bool operator < (edge a, edge b) {return a.lim < b.lim;} vector<pair<int, ll> > ans; int n, m, Q, x; int fa[N], a[N], og[N]; ll up[N]; int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);} int main() { freopen("poisoning.in" , "r" , stdin); freopen("poisoning.out" , "w", stdout); scanf("%d%d%d", &n, &m, &Q); FOR(i, 1, n) { scanf("%d", a + i); ans.push_back(mp(0, a[i])); } FOR(i, 1, m) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].lim); FOR(i, 1, n) fa[i] = i, up[i] = a[i], og[i] = 0; sort(e + 1, e + m + 1); FOR(i, 1, m) { int p = find(e[i].u), q = find(e[i].v); if (p == q) continue; og[q] = min(max((ll)og[p], e[i].lim - up[p]), max((ll)og[q], e[i].lim - up[q])); up[q] += up[p]; fa[p] = q; ans.push_back(mp(og[q], up[q])); } sort(ans.begin(), ans.end()); for(int i = 1; i < ans.size(); ++i) ans[i].second = max(ans[i].second, ans[i - 1].second); while (Q--) { scanf("%d", &x); printf("%d\n", (--upper_bound(ans.begin(), ans.end(), make_pair(x, inf))) -> second + x); } return 0; }
其中有许多玄学符号，接下来是网站大全：
vector：https://baike.baidu.com/item/vector/3330482?fr=aladdin
make_pair：https://blog.csdn.net/weixin_42825576/article/details/81571419
operator < (edge a, edge b) {return a.lim < b.lim;}：这是运算符重载
http://c.biancheng.net/view/2306.html
原文：https://www.cnblogs.com/qiuheqiuji/p/11178264.html