题解：AT_abc287_h [ABC287Ex] Directed Graph and Query

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

考虑 floyd 闭包。

因为

f_{k,i,j}

表示经过最大的编号为

k

，

i \sim j

是否联通（Floyd 闭包）。可以利用这个性质完成此题。

但如果预处理出

f_{k,i,j}

，空间就会飞起来。所以先存储查询，处理到一个

k

，检查查询是否满足条件，再干掉。这样就是滚动数组和离线化，同时完成了空间优化和时间优化。

时间复杂度：

\mathcal{O\left(\dfrac{n^3}{w}+qn\right)}

。

CPP

#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;
}

题解：AT_abc287_h [ABC287Ex] Directed Graph and Query

文章操作

相关推荐

评论

题解：AT_abc287_h [ABC287Ex] Directed Graph and Query