题解：P17195 [KOI 2026 #2] 游戏

· · 题解

题意简述

给定一张无向图。 一条边的权值表示两端房间间的通道数量。

每局游戏给定起点 s 与参数 k。 Alice 每次选择恰好 k 条相邻通道， Bob 决定她实际经过哪一条。

询问 Alice 能否保证到达某个出口。

解题思路

先固定参数 k。 把 Alice 能保证获胜的房间组成集合 S。

初始时，所有出口都属于 S。 若房间 u 通向 S 的通道总数不少于 k， 则可以把 u 加入 S。

Alice 只需选择其中任意 k 条通道。 Bob 无论选择哪一条， 都会把她送入一个已经属于 S 的房间。 所以，新加入的房间同样必胜。

不断执行这条规则，直到无法继续。 下面证明最终的 S 不会漏掉任何必胜房间。

对集合外的每个房间， 通向 S 的通道都少于 k 条。 若它一共不足 k 条通道，Alice 无法移动。

否则，Alice 选出的 k 条通道中， 至少有一条通向集合外。 Bob 始终选择这样的通道， 便能阻止 Alice 进入 S。

因此，上述闭包恰好等于必胜房间集合。

不同询问的闭包具有单调性。 参数越小，加入一个房间的条件越宽松。 所以，按 k 从大到小处理所有询问。

维护当前已经加入闭包的房间。 对每个尚未加入的房间 u，记：

d_u=\sum_{v\in S}c_{u,v}

其中 c_{u,v} 是两点间的通道数量。 当处理参数 k 时， 只要存在 d_u\ge k，就把 u 加入闭包。

房间 u 加入后， 遍历与它相邻且尚未加入的房间 v， 将 c_{u,v} 加入 d_v。

使用大根堆维护最大的 d_u。 同一房间更新后会在堆中留下旧记录。 弹出时比较记录值与当前 d_u， 即可丢弃这些过期记录。

下面说明降序处理始终得到正确闭包。

处理当前参数 k 前， 已有集合来自更大的参数。 由单调性，它一定包含于参数 k 的正确闭包。

随后不断加入满足 d_u\ge k 的房间。 这与固定 k 时的闭包扩张规则完全相同。 循环停止后，所有集合外房间都有 d_u<k。

所以，此时的集合既不会加入错误房间， 也已经达到参数 k 的唯一闭包。 直接检查起点是否在集合内即可回答询问。

每条无向边在某个端点加入时， 至多为另一个端点产生一次有效更新。 堆操作总数为 O(n+m)。

预处理与回答询问的总时间复杂度为：

O((n+m)\log(n+m)+q\log q)

空间复杂度为 O(n+m+q)。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=200005;
const int M=800005;
struct Query
{
    int s,id;
    ll k;
}ask[N];
int head[N],to[M],nxt[M],w[M],ec;
ll sum[N];
bool win[N],ans[N];
void add(int u,int v,int z)
{
    to[++ec]=v;
    w[ec]=z;
    nxt[ec]=head[u];
    head[u]=ec;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;
    cin>>n>>m>>q;
    for(int i=1;i<=n;i++)cin>>win[i];
    for(int i=1;i<=m;i++)
    {
        int u,v,z;
        cin>>u>>v>>z;
        add(u,v,z);
        add(v,u,z);
    }
    for(int i=1;i<=q;i++)
    {
        cin>>ask[i].s>>ask[i].k;
        ask[i].id=i;
    }
    sort(ask+1,ask+q+1,[](const Query &x,const Query &y){return x.k>y.k;});
    priority_queue<pair<ll,int>> h;
    for(int i=1;i<=n;i++)if(win[i])
    {
        for(int j=head[i];j;j=nxt[j])if(!win[to[j]])sum[to[j]]+=w[j];
    }
    for(int i=1;i<=n;i++)if(!win[i])h.push({sum[i],i});
    for(int i=1;i<=q;i++)
    {
        ll k=ask[i].k;
        while(1)
        {
            while(!h.empty()&&(win[h.top().second]||h.top().first!=sum[h.top().second]))h.pop();
            if(h.empty()||h.top().first<k)break;
            int u=h.top().second;
            h.pop();
            win[u]=1;
            for(int j=head[u];j;j=nxt[j])
            {
                int v=to[j];
                if(win[v])continue;
                sum[v]+=w[j];
                h.push({sum[v],v});
            }
        }
        ans[ask[i].id]=win[ask[i].s];
    }
    for(int i=1;i<=q;i++)cout<<(ans[i]?"YES":"NO")<<'\n';
    return 0;
}