首页 > 代码库 > L. Right Build bfs
L. Right Build bfs
http://codeforces.com/gym/101149/problem/L
给出一个有向图,从0开始,<u, v>表示要学会v,必须掌握u,现在要学会a和b,最小需要经过多少个点。
做这题的时候,一看就觉得是先找出a和b点的lca,但是以前学的LCA是树的,现在这个是图。
一定要知道LCA是树的,图的不行。
然后下午去上课了,图中找了一个博客里说,求有向图得lca可以反向建图 + bfs来搞,(当时还不清楚LCA是用在树上的,一直以为可以。)具体思路是对两个起点进行了bfs,然后拿她们的bfs序来判断相交在哪里。然后就搞了一个晚上了,最后发现是不行的,有数据保证不行,因为bfs的时候也有先后之分,这个先后和你的边顺序有关,就不能确定了
然后就想暴力吧,没一个a和b在反图上路径相同的点,都暴力去和答案更新最小值。
TLE几次后就能过了,预处理出数组就可以过。
给一些数据你们吧,找了一天的数据~~
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #define IOS ios::sync_with_stdio(false) using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> const int maxn = 5e5 + 20; struct node { int u, v, tonext; } e[maxn]; int num; int first[maxn]; int used; void add(int u, int v) { ++num; e[num].u = u; e[num].v = v; e[num].tonext = first[u]; first[u] = num; } int n, m, a, b; int ans; int book[maxn]; int zero[maxn]; struct bfsnode { int cur; int cnt; bfsnode(int a, int b) : cur(a), cnt(b) {} }; queue<struct bfsnode>que, quese; int bfs(int begin, int end, int DFN) { if (begin == end) return 0; book[begin] = DFN; while (!quese.empty()) quese.pop(); quese.push(bfsnode(begin, 0)); while (!quese.empty()) { struct bfsnode t = quese.front(); quese.pop(); for (int i = first[t.cur]; i; i = e[i].tonext) { int v = e[i].v; if (book[v] == DFN) continue; if (v == end) return t.cnt + 1; zero[v] = t.cnt + 1; book[v] = DFN; quese.push(bfsnode(v, t.cnt + 1)); } } return inf; } int first_two[maxn]; struct Edge { int u, v, tonext; } e_two[maxn]; int num_two; void add_two(int u, int v) { ++num_two; e_two[num_two].u = u; e_two[num_two].v = v; e_two[num_two].tonext = first_two[u]; first_two[u] = num_two; } int bookA[2][maxn]; int book_two[maxn]; void BFS(int begin, int DFN, int now) { while (!que.empty()) que.pop(); book_two[begin] = DFN; bookA[now][begin] = 0; if (bookA[!now][begin] != inf && zero[begin] != inf) { ans = min(bookA[now][begin] + bookA[!now][begin] + zero[begin], ans); } que.push(bfsnode(begin, 0)); while (!que.empty()) { struct bfsnode t = que.front(); que.pop(); for (int i = first_two[t.cur]; i; i = e_two[i].tonext) { int v = e_two[i].v; if (book_two[v] == DFN) continue; book_two[v] = DFN; bookA[now][v] = t.cnt + 1; if (bookA[!now][v] != inf && zero[v] != inf) { ++used; int tans = zero[v] + bookA[now][v] + bookA[!now][v]; ans = min(ans, tans); } que.push(bfsnode(v, t.cnt + 1)); } } return; } void find() { memset(bookA, 0x3f, sizeof bookA); ans = inf; used = 1; BFS(a, used, 0); ++used; BFS(b, used, 1); return; } int in[maxn]; void work() { IOS; cin >> n >> m >> a >> b; if (a == b) while(1); for (int i = 1; i <= m; ++i) { int u, v; cin >> u >> v; add(u, v); add_two(v, u); } memset(zero, 0x3f, sizeof zero); zero[0] = 0; bfs(0, inf, 8); find(); cout << ans << endl; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif work(); return 0; }
11 12 1 6
0 1
1 2
2 3
3 4
4 5
4 8
8 9
9 10
10 11
6 4
0 6
5 6
证明bfs找lca不行
7 14 10 7
0 1
1 2
2 3
3 4
3 5
5 6
9 10
4 5
5 7
1 8
8 7
4 5
6 9
8 6
证明普通LCA不行,因为lca用在树上
L. Right Build bfs
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。