树的直径

POJ-1985-Cow Marathon

树形DP

原理

见《进阶指南》第369页。

代码

#include <iostream>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 50010;
struct edge {
    int to, next, w;
};
edge e[2 * N];
int idx, head[N];
int n, m, res = -inf;
int d[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs (int cur, int fa) {
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to, w = e[i].w;
        if (to == fa) continue;
        dfs(to, cur);
        res = max(res, d[cur] + d[to] + w);
        d[cur] = max(d[cur], d[to] + w);
    }
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; ++ i) {
        char str[5];
        scanf("%d%d%d%s", &u, &v, &w, str);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    dfs(1, -1);
    printf("%d", res);
    return 0;
}

两次BFS

原理

见《进阶指南》第370页。

代码

#include <iostream>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 50010;
struct edge {
    int to, next, w;
};
edge e[2 * N];
int idx, head[N];
int n, m;
int dis[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
int bfs (int rt) {
    memset(dis, 0x3f, sizeof(dis));
    
    queue<int> q;
    dis[rt] = 0;
    q.push(rt);
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;
            if (dis[to] == inf) {
                dis[to] = dis[cur] + w;
                q.push(to);
            }
        }
    }
    int ver = 1;
    for (int i = 2; i <= n; ++ i)
        if (dis[i] > dis[ver])
            ver = i;
    return ver;
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; ++ i) {
        char str[5];
        scanf("%d%d%d%s", &u, &v, &w, str);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    printf("%d", dis[bfs(bfs(1))]);
    return 0;
}

两次DFS

原理

见《进阶指南》第370页。

代码

#include <iostream>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 50010;
struct edge {
    int to, next, w;
};
edge e[2 * N];
int idx, head[N];
int n, m;
int dis[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
void dfs (int cur, int fa) {
    for (int i = head[cur]; i != -1; i = e[i].next) {
        int to = e[i].to, w = e[i].w;
        if (to == fa) continue;
        dis[to] = dis[cur] + w;
        dfs(to, cur);
    }
}

int main () {
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1, u, v, w; i <= m; ++ i) {
        char str[5];
        scanf("%d%d%d%s", &u, &v, &w, str);
        add_edge(u, v, w);
        add_edge(v, u, w);
    }

    dis[1] = 0;
    dfs(1, -1);
    int ver = 1;
    for (int i = 2; i <= n; ++ i)
        if (dis[i] > dis[ver])
            ver = i;

    dis[ver] = 0;
    dfs(ver, -1);
    int res = -inf;
    for (int i = 1; i <= n; ++ i)
        res = max(res, dis[i]);
    printf("%d", res);
    return 0;
}