玛利亚∙多斯普拉泽雷斯-白红宇

玛利亚∙多斯普拉泽雷斯

阅读量：4358 次

发布时间：2019-06-07

本文共 2344 字，大约阅读时间需要 7 分钟。

公墓一共有 n 个墓地，通过 n−1 条通道相连。每次，推销员可以在选择一个墓地推销给玛利亚。
但是，考虑很多的玛利亚会尽量否决这个提议。她会选择一个墓地，否决掉它和与它相连的墓地。但为了礼仪，玛利亚不会选择推销员推销的或者已经被否决的墓地。
同样，为了礼仪，推销员也不会推销已经被否决的墓地。
如果某个被推销的墓地没有被否决，那么销售员就胜利了。否则玛利亚就胜利了。
除此之外，玛利亚可以在任意时间以洪水为借口删除一些通道，每次删除的通道数量也是任意的，不过删除的通道总数不能超过 K。两个墓地相连意味着这两个墓地由一条通道直接连接。
请判断双方都在最优策略下，谁能获胜。

博弈!!!!!!!

给出一棵树每次 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 
     
      #include 
      
       #include 
       
        #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
        
         
           > 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;}