题解：P11280 Jom & Terry

· · 题解

更新

前言

简单图上思维题。

周六的时候还在上课，语文课上拿着同学老年机看题并口胡，秒了。

约定

将 Jom 称为猫，将 Terry 称为鼠。
将鼠移动到根的所有路径中，必须经过的点称为关键点。
将图上两点 u,v 间的最小距离记为 \operatorname{dis}(u,v)。

思路

一个显然的结论是：如果猫能比鼠更早到一个关键点，那么猫就可以一直守在那里并且获胜。
另一个显然的结论是：根结点必定是关键点。

所以只要猫能比鼠更早到根节点，即 \operatorname{dis}(a,r)>\operatorname{dis}(b,r)，那么猫就赢了。

再考虑如果猫不能比鼠更早到根结点怎么办。
猜测结论：如果猫不能比鼠更早到根结点，那么鼠就赢了。考虑用反证法证明结论。

假设逆命题成立：猫不能比鼠更早到根结点，但猫可能会赢。

又一个显然的结论是：如果猫不能比鼠更早到任何一个关键点，那么鼠就赢了。
既然猫可能会赢，而“存在猫能比鼠更早到一个关键点”是“猫赢”的必要条件，那么说明存在一个关键点 u，使得猫到这个点的距离小于鼠到这个点的距离，即 \operatorname{dis}(a,u)>\operatorname{dis}(b,u)。
因为 u 对于鼠来说是关键点，所以 \operatorname{dis}(a,r)=\operatorname{dis}(a,u)+\operatorname{dis}(u,r)。
但是 u 对于猫来说不一定是去 r 的关键点，所以 \operatorname{dis}(b,r)\le\operatorname{dis}(b,u)+\operatorname{dis}(u,r)。
综合上面三个式子可得：\operatorname{dis}(b,r)<\operatorname{dis}(a,r)，即猫能比鼠更早到达根结点，与假设前提相冲突，所以假设不成立。

综上所述，如果猫能比鼠更早到根结点，那么猫就赢了；否则鼠就赢了。

以 r 为源点做一次 bfs 算出所有的 \operatorname{dis}(u,r)。询问的时候直接比较 \operatorname{dis}(a,u),\operatorname{dis}(b,u) 即可。

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

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e6+5;
int dis[MAXN];
vector<int>edg[MAXN];
queue<int>que;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int n,m,r; cin>>n>>m>>r;
    for(int i=1;i<=m;i++){
        int u,v; cin>>u>>v;
        edg[u].push_back(v);
        edg[v].push_back(u);
    }

    que.push(r);//bfs求出dis
    while(!que.empty()){
        int fr=que.front();
        que.pop();
        for(auto to:edg[fr]){
            if(to!=r&&dis[to]==0){
                dis[to]=dis[fr]+1;
                que.push(to);
            }
        }
    }

    int q; cin>>q;
    cout<<"I'm here!\n";
    while(q--){
        int a,b; cin>>a>>b;
        if(dis[b]<dis[a])cout<<"Jom\n";//直接比较
        else cout<<"Terry\n";
    }

    return 0;
}