首页 > 代码库 > hdu 3686 Traffic Real Time Query System 点双两通分量 + LCA
hdu 3686 Traffic Real Time Query System 点双两通分量 + LCA
http://acm.hdu.edu.cn/showproblem.php?pid=3686
我要把这题记录下来。
一直wa。
自己生成数据都是AC的。现在还是wa。留坑。
我感觉我现在倒下去床上就能睡着了。
不知道是我的LCA错了,还是tarjan
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <assert.h> #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> #include <bitset> const int maxm = 200000 + 20; const int maxn = 10000 + 20; struct Edge { int u, v, id, tonext; } e[maxm * 2]; int first[maxm], num; void addEdge(int u, int v, int id) { ++num; e[num].u = u, e[num].v = v, e[num].tonext = first[u]; first[u] = num; e[num].id = id; } int uuu[maxm], vvv[maxm]; int n, m; int low[maxm], DFN[maxm], st[maxm], id[maxm]; int top, when, toSelid; bool iscut[maxm]; vector<int>bolg[maxm]; int root; void tarjan(int cur, int fa) { DFN[cur] = low[cur] = ++when; int child = 0; for (int i = first[cur]; i; i = e[i].tonext) { int v = e[i].v; if (v == fa) continue; if (!DFN[v]) { child++; st[++top] = e[i].id; tarjan(v, cur); low[cur] = min(low[cur], low[v]); if (low[v] >= DFN[cur]) { iscut[cur] = true; // if (cur == root && child < 2) iscut[cur] = false; ++toSelid; do { int eID = st[top--]; bolg[uuu[eID]].push_back(toSelid); bolg[vvv[eID]].push_back(toSelid); id[eID] = toSelid; } while (st[top + 1] != e[i].id); } } else if (DFN[cur] > DFN[v]) { low[cur] = min(low[cur], DFN[v]); st[++top] = e[i].id; } } } void solveTarjan(int n) { memset(DFN, 0, sizeof DFN); memset(low, 0, sizeof low); memset(iscut, 0, sizeof iscut); memset(id, 0, sizeof id); for (int i = 1; i <= maxm - 2; ++i) { bolg[i].clear(); } when = top = toSelid = 0; for (int i = 1; i <= n; ++i) { if (!DFN[i]) { root = i; tarjan(i, i); } } } int dis[maxm]; bool treeCut[maxm], vis[maxm]; struct Node { int cur, cnt; Node(int _cur, int _cnt) { cur = _cur, cnt = _cnt; } }; void bfs(int be) { vis[be] = true; dis[be] = treeCut[be]; queue<struct Node>que; que.push(Node(be, treeCut[be])); while (!que.empty()) { struct Node t = que.front(); que.pop(); for (int i = first[t.cur]; i; i = e[i].tonext) { int v = e[i].v; if (vis[v]) continue; vis[v] = true; dis[v] = t.cnt + treeCut[v]; que.push(Node(v, t.cnt + treeCut[v])); } } } int ansc[maxn * 4][22], deep[maxm], fa[maxm]; void init_LCA(int cur) { ansc[cur][0] = fa[cur]; //跳1步,那么祖先就是爸爸 for (int i = 1; i <= 20; ++i) { //倍增思路,递归处理 ansc[cur][i] = ansc[ansc[cur][i - 1]][i - 1]; } for (int i = first[cur]; i; i = e[i].tonext) { int v = e[i].v; if (v == fa[cur]) continue; fa[v] = cur; deep[v] = deep[cur] + 1; init_LCA(v); } } int LCA(int x, int y) { if (deep[x] < deep[y]) swap(x, y); //需要x是最深的 for (int i = 20; i >= 0; --i) { //从大到小枚举,因为小的更灵活 if (deep[ansc[x][i]] >= deep[y]) { //深度相同,走进去就对了。就是要去到相等。 x = ansc[x][i]; } } if (x == y) return x; for (int i = 20; i >= 0; --i) { if (ansc[x][i] != ansc[y][i]) { //走到第一个不等的地方, x = ansc[x][i]; y = ansc[y][i]; } } return ansc[x][0]; //再跳一步就是答案 } void init() { num = 0; memset(ansc, 0, sizeof ansc); memset(deep, 0, sizeof deep); memset(fa, 0, sizeof fa); memset(dis, 0, sizeof dis); memset(treeCut, 0, sizeof treeCut); memset(vis, 0, sizeof vis); } void work() { init(); num = 0; memset(first, 0, sizeof first); for (int i = 1; i <= m; ++i) { int u, v; scanf("%d%d", &u, &v); addEdge(u, v, i); addEdge(v, u, i); uuu[i] = u; vvv[i] = v; } solveTarjan(n); memset(first, 0, sizeof first); memset(treeCut, 0, sizeof treeCut); num = 0; int to = toSelid; for (int i = 1; i <= n; ++i) { if (!iscut[i]) continue; ++to; treeCut[to] = true; sort(bolg[i].begin(), bolg[i].end()); addEdge(to, bolg[i][0], 1); addEdge(bolg[i][0], to, 1); for (int j = 1; j < bolg[i].size(); ++j) { if (bolg[i][j - 1] == bolg[i][j]) continue; addEdge(to, bolg[i][j], 1); addEdge(bolg[i][j], to, 1); } } // int tot = 2; // for (int i = 0; i < bolg[tot].size(); ++i) { // cout << bolg[tot][i] << " "; // } // cout << endl; memset(vis, false, sizeof vis); memset(fa, 0, sizeof fa); memset(deep, 0, sizeof deep); memset(ansc, 0, sizeof ansc); memset(dis, 0, sizeof dis); for (int i = 1; i <= to; ++i) { if (vis[i]) continue; bfs(i); fa[i] = i; deep[i] = 0; init_LCA(i); } // cout << iscut[11] << " ***" << endl; int q; scanf("%d", &q); while (q--) { int x, y; scanf("%d%d", &x, &y); x = id[x]; y = id[y]; if (x == y) { printf("0\n"); continue; } int res = LCA(x, y); if (res == x) { assert(treeCut[x] == 0); } if (res == y) { assert(treeCut[y] == 0); } int ans = dis[x] + dis[y] - 2 * dis[res]; assert(ans + treeCut[res] >= 0); printf("%d\n", ans + treeCut[res]); } } int main() { #ifdef local freopen("data.txt", "r", stdin); // freopen("data.txt", "w", stdout); #endif while (scanf("%d%d", &n, &m) != EOF && (n + m)) work(); return 0; }
hdu 3686 Traffic Real Time Query System 点双两通分量 + LCA
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。