AOJ 905.Ohyee的考验

121


题目



点击显/隐题目

有一个n个点m条边的连通无向图(无重边、无自环),点的编号为1~n。每条边都有一个正的边权,并且每条边边权互不相同(即数据保证该图的最小生成树唯一)。
如果只是求最小生成树,那么Ohyee觉得太简单了,于是他决定考考你。
对于每条边(u,v)都进行询问:
——如果该边在最小生成树上,那么输出“Ohyee”;
——如果该边不在最小生成树上,那么输出最小生成树上u,v两点路径中边权的最小值。
原图最小生成树中的边是(1,2,2) (2,3,5) (4,1,3)
对于输入的第三条边(3,4,7),树上3->4的路径是3->2->1->4,边权分别是5,2,3,最小值是2。


第一行输入两个整数n,m(2<=n<=100000,n-1<=m<=200000)
接下来m行,每行输入三个整数u,v,w。u,v表示该边连接点的编号,w是边权。
(1<=w<=1000000000)


输出一共m行,按照输入的边的顺序回答每条边的询问。


4 4
1 2 2
2 3 5
3 4 7
4 1 3


Ohyee
Ohyee
2
Ohyee




题解



前半部分很容易理解,最小生成树
后半部分要维护最小生成树上uv的路上最短的边(由于是一颗树,必然只有一条路)

由于数据量较大,一步一步找公共祖先不现实,需要倍增LCA



代码


点击显/隐代码
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;

#define Log(format, ...) // printf(format, ##__VA_ARGS__)

const int INF = 1000000005;
const int maxn = 1e5 + 5;
const int maxm = 2e5 + 5;
const int maxlog = 18;

int n,m;
int f[maxn];
bool use[maxm];

vector<int> edges[maxn];
int parent[maxn][maxlog];
int depth[maxn];
int weight[maxn][maxlog];

struct Edge {
    int u, v;
    int w;
    int n;
    bool operator<(const Edge rhs) const { return w < rhs.w; }
} e[maxm];
bool compare(Edge a, Edge b) { return a.n < b.n; }

int pos;
int ufs(int x) { return f[x] == x ? x : f[x] = ufs(f[x]); }
int Kruskal(int n, int m) {
    int w = 0;
    for (int i = 0; i <= n; i++)
        f[i] = i;
    sort(e, e + m);
    for (int i = 0; i < m; i++) {
        int x = ufs(e[i].u), y = ufs(e[i].v);
        // printf("%d %d\n", x, y);
        if (x != y) {
            f[x] = y;
            w += e[i].w;
            use[e[i].n] = true;
            edges[e[i].u].push_back(i);
            edges[e[i].v].push_back(i);
        }
    }
    return w;
}

void addEdge(int u, int v, int w, int number = 0) {
    e[pos].u = u;
    e[pos].v = v;
    e[pos].w = w;
    e[pos].n = number;
    pos++;
}

void dfs(int t, int deep) {
    depth[t] = deep;
    for (auto edge : edges[t]) {
        int child = e[edge].u ^ e[edge].v ^ t;
        if (parent[t][0] != child) {
            parent[child][0] = t;
            weight[child][0] = e[edge].w;
            dfs(child, deep + 1);
        }
    }
}

void lca() {
    for (int j = 1; j < maxlog; ++j) {
        for (int i = 1; i <= n; ++i) {
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
            weight[i][j] =
                min(weight[i][j - 1], weight[parent[i][j - 1]][j - 1]);
        }
    }
}

int query(int a, int b) {
    Log("Log(%d,%d)\n", a, b);

    int ans = INF;
    if (depth[a] < depth[b])
        swap(a, b);
    while (depth[a] != depth[b]) {
        int dis = depth[a] - depth[b];
        int step = (int)(log(dis) / log(2));
        Log("\t%d->%d (%d)\n", a, parent[a][step], weight[a][step]);
        ans =
            min(ans, weight[a][step]); // 由于这里还要用到a,因此a要在后面再赋值
        a = parent[a][step];
    }
    Log("\tthe same depth %d %d\n", a, b);
    while (a != b) {
        int step = 0;
        for (int i = 0; i < maxlog; ++i) {
            if (parent[a][i] == parent[b][i]) {
                step = i - (i ? 1 : 0);
                break;
            }
        }
        Log("\tstep: %d a: %d->%d (%d)  b: %d->%d (%d)\n", step, a,
            parent[a][step], weight[a][step], b, parent[b][step],
            weight[b][step]);
        ans = min(ans, min(weight[a][step], weight[b][step]));
        a = parent[a][step];
        b = parent[b][step];
    }
    return ans;
}

/*
void lca(int t, int deep) {
    depth[t] = deep;
    vector<int>::iterator it = edges[t].begin();
    while (it != edges[t].end()) {
        int v = e[*it].u ^ e[*it].v ^ t;
        if (parent[t] != v) {
            parent[v] = t;
            weight[v] = e[*it].w;
            lca(v, deep + 1);
        }
        ++it;
    }
}

int query(int a, int b, int n) {
    int ans = INF;
    // printf("%d %d\n", a, b);
    if (depth[a] > depth[b])
        swap(a, b);

    while (depth[b] != depth[a]) {
        // printf("%d -> %d (%d)\n", b, parent[b], weight[b]);
        ans = min(ans, weight[b]);
        b = parent[b];
    }
    // printf("%d %d\n", a, b);
    while (a != b) {
        // printf("%d -> %d (%d)\n", a, parent[a], weight[a]);
        ans = min(ans, weight[a]);
        a = parent[a];

        // printf("%d -> %d (%d)\n", b, parent[b], weight[b]);
        ans = min(ans, weight[b]);
        b = parent[b];
    }

    return ans;
}
*/

int main() {
    // int size = 256 << 20; // 256MB
    // char *p = (char *)malloc(size) + size;
    //__asm__("movl %0, %%esp\n" ::"r"(p));

    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    while (~scanf("%d%d", &n, &m)) {
        memset(use, false, (m + 5) * sizeof(bool));
        for (int i = 0; i <= n; ++i)
            edges[i].clear();

        for (int i = 0; i < m; ++i) {
            int u, v, w;
            scanf("%d%d%d", &u, &v, &w);
            addEdge(u, v, w, i);
        }
        // printf("read finish\n");
        // printf("%d\n", Kruskal(n, m));
        Kruskal(n, m);
        // printf("build tree finish\n");

        parent[1][0] = 0;
        weight[1][0] = INF;
        dfs(1, 0);
        lca();

        sort(e, e + m, compare);

        for (int i = 0; i < m; ++i) {
            if (use[i]) {
                printf("Ohyee\n");
            } else {
                printf("%d\n", query(e[i].u, e[i].v));
            }
        }
    }

    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论