题解：AT_abc287_h [ABC287Ex] Directed Graph and Query

细数繁星 · 2025-10-31 19:16:12 · 题解

当时我脑抽了，竟然想到了诈骗机构某年的货车运输。

考虑 floyd 闭包。

因为 f_{k,i,j} 表示经过最大的编号为 k，i \sim j 是否联通（Floyd 闭包）。可以利用这个性质完成此题。

但如果预处理出 f_{k,i,j}，空间就会飞起来。所以先存储查询，处理到一个 k，检查查询是否满足条件，再干掉。这样就是滚动数组和离线化，同时完成了空间优化和时间优化。

时间复杂度：\mathcal{O\left(\dfrac{n^3}{w}+qn\right)}。

#include <bits/stdc++.h>
#define rty printf("Yes\n");
#define RTY printf("YES\n");
#define rtn printf("No\n");
#define RTN printf("NO\n");
#define rep(v,b,e) for(int v=b;v<=e;v++)
#define repq(v,b,e) for(int v=b;v<e;v++)
#define rrep(v,e,b) for(int v=b;v>=e;v--)
#define rrepq(v,e,b) for(int v=b;v>e;v--)
#define stg string
#define vct vector
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void solve() {

}

int s[10005], t[10005], ans[10005];
bitset<2005> floyd[2005];

main() {
//  int t; cin >> t; while (t--) solve();
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
    int n, m;
    cin >> n >> m;
    rep(i, 1, m) {
        int u, v;
        cin >> u >> v;
        floyd[u][v] = 1;
    }
    int q;
    cin >> q;
    rep(i, 1, q) {
        cin >> s[i] >> t[i];
        ans[i] = -1;
    }
    rep(k, 1, n) {
        rep(i, 1, n) 
            if (floyd[i][k]) floyd[i] |= floyd[k];
        rep(i, 1, q)
            if (ans[i] == -1 && floyd[s[i]][t[i]])
                ans[i] = max({k, s[i], t[i]});
    }
    rep(i, 1, q)
        cout << ans[i] << '\n';
    return 0;
}