题解：P10231 [COCI 2023/2024 #4] Putovanje

根号分治的思想 （乱搞做法）。

首先，你会容易想出一个暴力，跑有距离限制的城市的最短路，然后对所有满足限制的城市取个交集。由于边权只为 1，所以跑 bfs 即可。

时间 O(n^2)，能得到部分分。缺点是当 d 数组的限制过多时，时间会被卡满。

然后，你又会想出另一个暴力，跑答案。也就是对于每个点，我们去跑最短路，然后判断是否与限制相符。

时间同样是 O(n^2)。但缺点是当 d 数组的限制过少时，答案可能性会变多。所以我们跑的就很多。

考虑结合下两个做法。

我们先跑一些城市，得到一些答案。然后对答案跑城市的限制即可。

实现上，注意限制全为 -1 和有 0 的情况，不然会被捆成 dog。

hack 是好造的，菊花图能够卡满，但鉴于 O(n^2) 再加上一些优化，是可以通过的。

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 2e5 + 15;

vector<int> g, vec[N], ans;

void add(int x, int y) {
    vec[x].push_back(y);
}

int x[N], mp[N], p[N], tot;

int d[N]; 
bool vis[N];

void bfs(int st, int dist) {
    queue<int> q;
    memset(d, 0x3f, sizeof d);
    memset(vis, 0, sizeof vis);
    q.push(st);
    d[st] = 0;
    while(q.size()) {
        int x = q.front(); q.pop();
        if(vis[x]) continue;
        vis[x] = true;
        for(int v : vec[x]) {
            if(d[v] > d[x] + 1) {
                d[v] = d[x] + 1;
                q.push(v);
            }
        }
        if(d[x] > dist + 10) return ;
    }
}

double t;

void check() {
    for(int i = 1; i <= tot; i ++) {
        bfs(p[i], 1000000);
        bool f = 1;
        for(int j : g) {
            if(x[j] != d[j]) {
                f = 0;
                break;
            }
        }
        if(f) ans.push_back(p[i]);
    }
    cout << ans.size() << "\n";
    for(int i : ans) cout << i << " ";
}

int main() {
    freopen("putovanje.in","r",stdin);
    freopen("putovanje.out","w",stdout);
    int n, m;
    cin >> n >> m;
    t = clock(); 
    for(int i = 1; i <= m; i ++) {
        int u, v;
        scanf("%d%d", &u, &v);
        add(u, v);
        add(v, u);
    }
    for(int i = 1; i <= n; i ++) {
        scanf("%d", &x[i]);
        if(x[i] != -1) g.push_back(i);
    }
    int cnt = 0;
    for(int i : g) {
        bfs(i, x[i]);
        cnt ++;
        tot = 0;
        for(int j = 1; j <= n; j ++) {
            if(d[j] == x[i]) mp[j] ++;
            if(mp[j] == cnt && (x[j] == -1 || x[j] == 0)) p[++ tot] = j;
        }
        if(cnt == g.size() || clock() - t >= 1990 * 1000) {
            cout << tot << "\n";
            for(int j = 1; j <= tot; j ++) {
                cout << p[j] << ' ';
            }
            return 0;
        }
        if(tot <= 1000) {
            check();
            return 0;
        }
    }
    if(tot) {
        check();
        return 0;
    }
    int ans = 0;
    for(int i = 1; i <= n; i ++) {
        if(vec[i].size()) ans ++;
    } 
    cout << ans << "\n";
    for(int i = 1; i <= n; i ++) {
        if(vec[i].size()) cout << i << " ";
    }
    return 0;
}