ACM-ICPC 2018 徐州赛区网络预赛 J. Maze Designer

传送门：https://nanti.jisuanke.com/t/31462

本题是一个树上的问题：结点间路径问题。

给定一个有N×M个结点的网格，并给出结点间建立墙（即拆除边）的代价。花费最小的代价，使得每一对结点之间的路径唯一。给出Q次询问：每次询问一对结点的路径长度。

每一对结点之间存在路径，则图是连通的；路径唯一，则图是无环的。于是拆除边后的图是原图的一棵生成树。为使得拆除的代价尽可能小，这棵生成树应是最大生成树。通过Kruskal算法，可以求解最大生成树。

之后，即是询问树结点对的路径长度。这个问题可以通过LCA算法求解。

设结点u、v的LCA为结点k，即k=LCA(u,v)，则dis(u,v)=dep[u]+dep[v]-2*dep[k]。此处通过倍增实现LCA。

参考程序如下：

#include <bits/stdc++.h>

using namespace std;

#define MAX_N 300005

priority_queue<pair<int, pair<int, int> > > edge;

vector<int> adj[MAX_N];

//Union Find.

int fa[MAX_N];

void init_dset(int n)

{

    for (int i = ; i < n; i++) fa[i] = i;

}

int find(int u)

{

    if (fa[u] == u) return u;

    return fa[u] = find(fa[u]);

}

void unite(int u, int v)

{

    int fu = find(u), fv = find(v);

    if (fu == fv) return;

    fa[fu] = fv;

}

bool same(int u, int v)

{

    return find(u) == find(v);

}

//LCA.

int pre[][MAX_N]; //Ancestor Nodes.

int dep[MAX_N]; //Depth of Nodes.

void dfs(int u, int p)

{

    pre[][u] = p;

    for (int v : adj[u]) {

        if (v != p) {

            dep[v] = dep[u] + ;

            dfs(v, u);

        }

    }

}

void init_lca(int n)

{

    dfs(, -);

    for (int k = ; k < ; k++) {

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

            if (pre[k][v]) pre[k + ][v] = pre[k][pre[k][v]];

        }

    }

}

int lca(int u, int v)

{

    if (dep[u] > dep[v]) swap(u, v);

    for (int k = ; k < ; k++) {

        if ((dep[v] - dep[u]) & ( << k)) v = pre[k][v];

    }

    if (u == v) return u;

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

        if (pre[k][u] != pre[k][v]) {

            u = pre[k][u];

            v = pre[k][v];

        }

    }

    return pre[][u];

}

int main(void)

{

    ios::sync_with_stdio(false);

    int n, m;

    cin >> n >> m;

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

        for (int j = ; j < m; j++) {

            string s, t;

            int a, b;

            cin >> s >> a >> t >> b;

            if (s[] == 'D') {

                int u = i * m + j;

                int v = (i + ) * m + j;

                edge.push(make_pair(a, make_pair(u, v)));

            }

            if (t[] == 'R') {

                int u = i * m + j;

                int v = i * m + j + ;

                edge.push(make_pair(b, make_pair(u, v)));

            }

        }

    }

    init_dset(n * m);

    while (!edge.empty()) {

        auto e = edge.top();

        edge.pop();

        int u = e.second.first;

        int v = e.second.second;

        if (!same(u, v)) {

            unite(u, v);

            adj[u].push_back(v);

            adj[v].push_back(u);

        }

    }

    init_lca(n * m);

    int q;

    cin >> q;

    while (q--) {

        int a, b, c, d;

        cin >> a >> b >> c >> d;

        a--; b--; c--; d--;

        int u = a * m + b;

        int v = c * m + d;

        int k = lca(u, v);

        cout << dep[u] + dep[v] -  * dep[k] << endl;

    }

}

巴特西

ACM-ICPC 2018 徐州赛区网络预赛 J. Maze Designer

最新文章

热门文章