题解 P5145 【漂浮的鸭子】

· · 题解

广告时间：

安利\tt{BLOG}

下面我们进入正题：

题目中要求求出最大环，我们可以用tarjan求出强连通分量来解决。

关于边权，我们可以把它转换为点权，然后再在每个强连通分量里进行求和，求出最大的值。

需要注意的一点就是当把边权转换为点权时，不能把边权赋给去的点，要把边权付给这条边的源点。

就是因为这个所以我才WA了一次，错失了一遍AC的机会

上代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN 1000100
struct Edge {
    int v, nx;
}e[MAXN];
inline int min(int a, int b) {
    if (a < b) return a;
    else return b;
}
inline int max(int a, int b) {
    if (a > b) return a;
    else return b;
}
int head[MAXN], tim, st[MAXN], top, ecnt, n, m, x, y, dfn[MAXN], low[MAXN], in[MAXN], si[MAXN], num, se[MAXN], ans;
bool vis[MAXN];
void add(int f, int t) {
    e[++ecnt] = (Edge) {t, head[f]};
    head[f] = ecnt;
}
void tarjan(int u) {
    dfn[u] = low[u] = ++tim;
    st[++top] = u;
    vis[u] = 1;
    for (int i = head[u]; i; i = e[i].nx) {
        int v = e[i].v;
        if (!dfn[v]) {
            tarjan(v);
            low[u] = min(low[v], low[u]);
        }
        else if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (low[u] == dfn[u]) {
        int v;
        num++;
        do {
            v = st[top--];
            in[v] = num;
            vis[v] = 0;
            si[num] += se[v];
        } while (u != v);
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d", &x, &y);
        add(i, x);
        se[i] = y;
    }
    for (int i = 1; i <= n; i++) {
        if (!dfn[i]) tarjan(i);
    }
    for (int i = 1; i <= num; i++) {
        ans = max(ans, si[i]);
    }
    printf("%d\n", ans);
    return 0;
}

不过我看好多人的提交记录都是直接用一个dfs解决的，难道我想复杂了？