SPOJ Two Paths

Description

给定一个无向图，含有一定的路。从中找出两个最长的路径（每条路径有一些相通路组成）这两个路径不能经过公共的点，求何时二路径的乘积最大。

本题给出的无向图是一棵树，每边权值为1.

原文翻译应为有n个点，n-1条边，两点之间能够相互到达。

Solution

直径分成两部分得到的两条路径
直径的一部分和另一部分里的最长链

Code

#include <vector>

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

const int N = 100005;

namespace { // 此处应该替换为Class Solution

    int n, dep[N], fa[N], MxDepP;

    int dis[N], cnt, d[N], ind[N];

    int L[N], R[N];

    std:: vector<int> e[N];

    void dfs1(int u, int fath) {

        dep[u] = dep[fath] + 1, fa[u] = fath;

        for (auto v : e[u])

            if (v != fath)

                dfs1(v, u);

        if (dep[u] > dep[MxDepP])

            MxDepP = u;

    }

    void dfs2(int u, int fath) {

        for (int v : e[u])

            if (v != fath and not ind[v])

                dfs2(v, u), dis[u] = std:: max(dis[u], dis[v] + 1);

    }

    int GetDiameter() {

        dfs1(1, 0);

        dfs1(MxDepP, 0);

        int end = MxDepP;

        while(end)

            d[++cnt] = end, ind[end] = true, end = fa[end];

    }

    long long CalcAnswer() {

        long long Res = 0;

        for (int i = 1; i <= cnt; i += 1) {

            dfs2(d[i], 0);

            Res = std:: max(Res, 1ll * (dis[d[i]] - 1) * (cnt - 1));

        }

        int tmp = 0;

        for (int i = 1; i <= cnt; i += 1)

            L[i] = tmp = std:: max(tmp, i - 2 + dis[d[i - 1]]);

        tmp = 0;

        for (int i = cnt; i >= 1; i -= 1)

            R[i] = tmp = std:: max(tmp, cnt - i + dis[d[i + 1]] - 1);

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

            Res = std:: max(Res, 1ll * L[i] * R[i - 1]);

        return Res;

    }

};

int main () {

    scanf("%d", &n);

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

        int u, v;

        scanf("%d%d", &u, &v);

        e[u].push_back(v), e[v].push_back(u);

    }

    GetDiameter();

    printf("%lld\n", CalcAnswer());

    return 0;

}

巴特西

SPOJ Two Paths

Description

Solution

Code

最新文章

热门文章