[SMOJ1831]小島II

看到這題，我首先想到是參考之前所做的“最優貿易”一題，但是事實上兩題的做法是大相徑庭的。

一點一點來分解題目，我們就能夠有一個比較清晰的思路。

首先，價值可能為負數，而經過結點是可以取也可以不取，那麼顯然不應該取負數。

從任意結點出發，在任意結點停止。也就是說，對于一個環，我們愛怎麼走就怎麼走。顯然最優方案，應該把一個強連通分量内權值為正數的點都要取一遍。

跟之前題目的政策類似，對于有向圖上的最優值問題，可以考慮一下：是否可以将圖縮點，然後利用拓撲圖的性質，做一些 DP，或是搜尋？

因為是從任意點開始，任意點結束。在一個有向圖中，相對來說，考慮目前結點的前驅結點能夠到達目前結點，進而用目前結點的值去改進或更新前驅結點的值，是一種比較好的政策。同時，我們知道，如果固定從某個點開始，那麼就可以看作一個确定的子問題，當它的值求得之後，無論是從哪個前驅結點到達目前結點，之後能取得的最優值都是确定的。

綜上所述，就可以枚舉起點，之後用記憶化搜尋的方式，計算 fi 表示從結點 i 出發能取得的價值和。枚舉一下起點，就可以在 O(n) 的時間内得到最優值。再算上前面的 tarjan 縮點，可以線上性時間内解決本題。

如果拓展一下，想一想是否可以用 spfa 搞呢？

本題是不太适合的。因為 spfa 的松弛裡面可能出現多次取同一結點價值的情況，如果再加個狀态記錄顯然是不現實的。是以要分析題目，各種角度考慮做法，切忌思維定式。同時還是那句話，積累解決同一類題目的常見政策。

參考代碼：

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <stack>
#include <queue>

using namespace std;

const int maxn = 1e5 + 100;

struct Edge { int to, next; } edge[maxn], edge1[maxn];
int cntEdge, cntEdge1;
int a[maxn], b[maxn];

int n, m;
int value[maxn], belong[maxn];

int head[maxn], head1[maxn];
void addEdge(int u, int v) {
    edge[++cntEdge].to = v;
    edge[cntEdge].next = head[u];
    head[u] = cntEdge;
}
void addEdge1(int u, int v) {
    edge1[++cntEdge1].to = v;
    edge1[cntEdge1].next = head1[u];
    head1[u] = cntEdge1;
}

int timeStamp;
int dfn[maxn], low[maxn];
int cntScc;
bool instack[maxn];
stack <int> st;

int val[maxn];

void tarjan(int root) {
    dfn[root] = low[root] = ++timeStamp;
    instack[root] = true;
    st.push(root);
    for (int i = head[root]; i; i = edge[i].next) {
        int To = edge[i].to;
        if (!dfn[To]) { tarjan(To); low[root] = min(low[root], low[To]); }
        else if (instack[To]) low[root] = min(low[root], dfn[To]);
    }
    if (dfn[root] == low[root]) {
        ++cntScc;
        int cur;
        do {
            cur = st.top(); st.pop();
            instack[cur] = false;
            belong[cur] = cntScc;
        }
        while (cur != root);
    }
}

int dp[maxn];
int ans;
bool vis[maxn]; //記憶化，搜尋過的标記

void dfs(int r) {
    if (vis[r]) return; else vis[r] = true;
    for (int i = head1[r]; i; i = edge1[i].next) {
        dfs(edge1[i].to);
        dp[r] = max(dp[r], dp[edge1[i].to]);
    }
    dp[r] += val[r];
}

int main(void) {
    freopen("1831.in", "r", stdin);
    freopen("1831.out", "w", stdout);
    int r;
    scanf("%d", &r);
    while (r--) {
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) scanf("%d", &value[i]);
        memset(head, 0, sizeof head);
        cntEdge = 0;
        for (int i = 0; i < m; i++) {
            scanf("%d%d", &a[i], &b[i]);
            addEdge(a[i], b[i]);
        }
        timeStamp = cntScc = 0;
        memset(dfn, 0, sizeof dfn);
        memset(val, 0, sizeof val);
        while (!st.empty()) st.pop();
        memset(belong, 0, sizeof belong);
        for (int i = 0; i < n; i++) if (!dfn[i]) tarjan(i);
        memset(head1, 0, sizeof head1);
        cntEdge1 = 0;
        for (int i = 0; i < n; i++) { //縮點後重新構圖
            for (int j = head[i]; j; j = edge[j].next)
                if (belong[i] != belong[edge[j].to]) addEdge1(belong[i], belong[edge[j].to]);
            if (value[i] > 0) val[belong[i]] += value[i]; //正數才取
        }
        memset(dp, 0, sizeof dp);
        memset(vis, false, sizeof vis);
        ans = 0;
        for (int i = 1; i <= cntScc; i++) { //考慮從每一個強連通分量出發
            dfs(i);
            ans = max(ans, dp[i]);
        }
        printf("%d\n", ans);
    }
    return 0;
}