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 =  + ;

const int maxn =  + ;

struct Edge {

    int u, v, id, tonext;

} e[maxm * ];

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 = ;

    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 + ] != 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, , sizeof DFN);

    memset(low, , sizeof low);

    memset(iscut, , sizeof iscut);

    memset(id, , sizeof id);

    for (int i = ; i <= maxm - ; ++i) {

        bolg[i].clear();

    }

    when = top = toSelid = ;

    for (int i = ; 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 * ][], deep[maxm], fa[maxm];

void init_LCA(int cur) {

    ansc[cur][] = fa[cur]; //跳1步，那么祖先就是爸爸

    for (int i = ; i <= ; ++i) { //倍增思路，递归处理

        ansc[cur][i] = ansc[ansc[cur][i - ]][i - ];

    }

    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] + ;

        init_LCA(v);

    }

}

int LCA(int x, int y) {

    if (deep[x] < deep[y]) swap(x, y); //需要x是最深的

    for (int i = ; i >= ; --i) { //从大到小枚举，因为小的更灵活

        if (deep[ansc[x][i]] >= deep[y]) { //深度相同，走进去就对了。就是要去到相等。

            x = ansc[x][i];

        }

    }

    if (x == y) return x;

    for (int i = ; i >= ; --i) {

        if (ansc[x][i] != ansc[y][i]) { //走到第一个不等的地方，

            x = ansc[x][i];

            y = ansc[y][i];

        }

    }

    return ansc[x][]; //再跳一步就是答案

}

void init() {

    num = ;

    memset(ansc, , sizeof ansc);

    memset(deep, , sizeof deep);

    memset(fa, , sizeof fa);

    memset(dis, , sizeof dis);

    memset(treeCut, , sizeof treeCut);

    memset(vis, , sizeof vis);

}

void work() {

    init();

    num = ;

    memset(first, , sizeof first);

    for (int i = ; 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, , sizeof first);

    memset(treeCut, , sizeof treeCut);

    num = ;

    int to = toSelid;

    for (int i = ; i <= n; ++i) {

        if (!iscut[i]) continue;

        ++to;

        treeCut[to] = true;

        sort(bolg[i].begin(), bolg[i].end());

        addEdge(to, bolg[i][], );

        addEdge(bolg[i][], to, );

        for (int j = ; j < bolg[i].size(); ++j) {

            if (bolg[i][j - ] == bolg[i][j]) continue;

            addEdge(to, bolg[i][j], );

            addEdge(bolg[i][j], to, );

        }

    }

//    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, , sizeof fa);

    memset(deep, , sizeof deep);

    memset(ansc, , sizeof ansc);

    memset(dis, , sizeof dis);

    for (int i = ; i <= to; ++i) {

        if (vis[i]) continue;

        bfs(i);

        fa[i] = i;

        deep[i] = ;

        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] == );

        }

        if (res == y) {

            assert(treeCut[y] == );

        }

        int ans = dis[x] + dis[y] -  * dis[res];

        assert(ans + treeCut[res] >= );

        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 ;

}

原来这题是有重边的，怪不得我一直wa。而且自己生成的数据都是没有重边的，TAT

说下思路，

题目要求的经过多少个割点，

首先，题目给出的是从边s走到边t。这样很好办，一开始以为是点s做到点t，这样比较麻烦。

先做一次点双连通分量，对边分好id。然后对于每一个割点，把和它连接的边重建一颗树。然后这个割点就是这棵树的treeCut

这就相当于给出一颗树，树上有些点（那副图的边变成点了）是染色了的，问从点s走到点t，最少走过多少个染色的点。

这样可以预处理出dis[i]表示从树根走到点i，一共经过多少个染色的点，这样就相当于区间减法，然后配合lca即可。

1、题目虽然保证roads到rodat有路，但是可能有多个连通分支。

2、有重边。

其实有重边不用怕，没什么的，只需要标记那条边是用过了的就可以。

既可以判断不返回fa，又可以判重边。

#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 =  + ;

const int maxn =  + ;

struct Edge {

    int u, v, id, tonext;

} e[maxm * ];

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, int fromID) {

    DFN[cur] = low[cur] = ++when;

    int child = ;

    for (int i = first[cur]; i; i = e[i].tonext) {

        int v = e[i].v;

        if (v == fa && e[i].id == fromID) continue;

        if (!DFN[v]) {

            child++;

            st[++top] = e[i].id;

            tarjan(v, cur, e[i].id);

            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 + ] != 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, , sizeof DFN);

    memset(low, , sizeof low);

    memset(iscut, , sizeof iscut);

    memset(id, , sizeof id);

    for (int i = ; i <= maxm - ; ++i) {

        bolg[i].clear();

    }

    when = top = toSelid = ;

    for (int i = ; 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 * ][], deep[maxm], fa[maxm];

void init_LCA(int cur) {

    ansc[cur][] = fa[cur]; //跳1步，那么祖先就是爸爸

    for (int i = ; i <= ; ++i) { //倍增思路，递归处理

        ansc[cur][i] = ansc[ansc[cur][i - ]][i - ];

    }

    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] + ;

        init_LCA(v);

    }

}

int LCA(int x, int y) {

    if (deep[x] < deep[y]) swap(x, y); //需要x是最深的

    for (int i = ; i >= ; --i) { //从大到小枚举，因为小的更灵活

        if (deep[ansc[x][i]] >= deep[y]) { //深度相同，走进去就对了。就是要去到相等。

            x = ansc[x][i];

        }

    }

    if (x == y) return x;

    for (int i = ; i >= ; --i) {

        if (ansc[x][i] != ansc[y][i]) { //走到第一个不等的地方，

            x = ansc[x][i];

            y = ansc[y][i];

        }

    }

    return ansc[x][]; //再跳一步就是答案

}

void work() {

    num = ;

    memset(first, , sizeof first);

    for (int i = ; 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, , sizeof first);

    memset(treeCut, , sizeof treeCut);

    num = ;

    int to = toSelid;

    for (int i = ; i <= n; ++i) {

        if (!iscut[i]) continue;

        ++to;

        treeCut[to] = true;

        sort(bolg[i].begin(), bolg[i].end());

        addEdge(to, bolg[i][], );

        addEdge(bolg[i][], to, );

        for (int j = ; j < bolg[i].size(); ++j) {

            if (bolg[i][j - ] == bolg[i][j]) continue;

            addEdge(to, bolg[i][j], );

            addEdge(bolg[i][j], to, );

        }

    }

//    int tot = 2;

//    for (int i = 0;  i < bolg[tot].size(); ++i) {

//        cout << bolg[tot][i] << " ";

//    }

//    cout << endl;

    memset(vis, false, sizeof vis);

    for (int i = ; i <= to; ++i) {

        if (vis[i]) continue;

        bfs(i);

        fa[i] = i;

        deep[i] = ;

        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] == );

        }

        if (res == y) {

            assert(treeCut[y] == );

        }

        int ans = dis[x] + dis[y] -  * dis[res];

        assert(ans + treeCut[res] >= );

        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 ;

}

代码写的很烂，因为wa了3小时，一直在yy改错。