题解 CF1790G 【Tokens on Graph】

Leasier · 2023-07-19 09:44:07 · 题解

这道 3G 就算不考虑 WA on 1 那一发我还是 WA 了两发，没救了 /kk

考虑一条符合条件的路径：u \to p_1 \to p_2 \to \cdots p_k \to 1，其中 p_1, p_2, \cdots, p_k 均为 bonus。

那在走这条路径时，我们需要其他棋子干啥呢？除了第一步 u \to p_1，后面每一步都需要其他棋子走一步才能接着走。

考虑从 1 开始 bfs 求出其到每个点只走 bonus 的最短路，现在我们还需要知道从每个点出发只走 bonus 至多走几步，设之为 v_u。

此时走不动，则 v_u = 0。

此时只能走一步，则 v_u = 1。

此时可以反复横跳，则 v_u = +\infty。

于是可以求得其他棋子可以提供的步数，即其 v_i 之和。

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

代码：

#include <iostream>
#include <queue>
#include <cstdio>

using namespace std;

typedef long long ll;

typedef struct {
    int nxt;
    int end;
} Edge;

int cnt;
int head[200007], bucket[200007], dis[200007], val[200007];
bool bonus[200007], inf[200007];
Edge edge[400007];
queue<int> q;

inline void init(int n){
    cnt = 0;
    for (int i = 1; i <= n; i++){
        head[i] = bucket[i] = 0;
        dis[i] = 0x7fffffff;
        bonus[i] = false;
    }
}

inline void add_edge(int start, int end){
    cnt++;
    edge[cnt].nxt = head[start];
    head[start] = cnt;
    edge[cnt].end = end;
}

inline void bfs(int start){
    dis[start] = 0;
    q.push(start);
    while (!q.empty()){
        int cur = q.front(), dis_i = dis[cur] + 1;
        q.pop();
        for (int i = head[cur]; i != 0; i = edge[i].nxt){
            int x = edge[i].end;
            if (bonus[x] && dis[x] == 0x7fffffff){
                dis[x] = dis_i;
                q.push(x);
            }
        }
    }
}

int main(){
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= t; i++){
        int n, m, p, b;
        scanf("%d %d", &n, &m);
        scanf("%d %d", &p, &b);
        init(n);
        for (int j = 1; j <= p; j++){
            int x;
            scanf("%d", &x);
            bucket[x]++;
        }
        for (int j = 1; j <= b; j++){
            int x;
            scanf("%d", &x);
            bonus[x] = true;
        }
        for (int j = 1; j <= m; j++){
            int u, v;
            scanf("%d %d", &u, &v);
            add_edge(u, v);
            add_edge(v, u);
        }
        if (bucket[1] > 0){
            cout << "YES" << endl;
            continue;
        }
        ll sum = 0;
        bool ans = false;
        for (int j = 1; j <= n; j++){
            if (bonus[j]){
                inf[j] = false;
                for (int k = head[j]; k != 0; k = edge[k].nxt){
                    int x = edge[k].end;
                    if (bonus[x]){
                        inf[j] = true;
                        break;
                    }
                }
            }
        }
        for (int j = 1; j <= n; j++){
            val[j] = 0;
            for (int k = head[j]; k != 0; k = edge[k].nxt){
                int x = edge[k].end;
                if (bonus[x]){
                    if (!inf[x]){
                        val[j] = max(val[j], 1);
                    } else {
                        val[j] = 0x7fffffff;
                    }
                }
            }
        }
        for (int j = 2; j <= n; j++){
            sum += (ll)bucket[j] * val[j];
        }
        bfs(1);
        for (int j = 2; j <= n && !ans; j++){
            if (bucket[j] > 0){
                for (int k = head[j]; k != 0; k = edge[k].nxt){
                    int x = edge[k].end;
                    if (x == 1 || (bonus[x] && dis[x] != 0x7fffffff && sum - val[j] >= dis[x])){
                        ans = true;
                        break;
                    }
                }
            }
        }
        if (ans){
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}