LA 6800 The Mountain of Gold?（BellmanFord判負環+記憶化搜索）

LA 6800 The Mountain of Gold?（BellmanFord判負環+記憶化搜索）

6800 - The Mountain of Gold?

題目大意：

給定一張有向圖，問能否從0號點出發，回到0號點，經過的路徑上邊權之和小於0。若可能，輸出“possible”，否則輸出“not possible”。

解題思路：

Bellman Ford算法不但可以計算單源最短路徑，還可以應用於判斷：從源點出發，是否能夠到達一個負環。

應用於本題，因為只要從0出發，能夠到達一個負環，並且還能走回的話，就能實現要求（負環外的邊權不用考慮，在負環內多走幾圈，肯定能使總邊權小於0）。所以用Bellman Ford找出所有從0出發能到達的負環，再用記憶化搜索的方法，判斷負環上的任意一點，是否與0相連。一個點能與0相連，那麼與這個點相連的點，也能與0相連（注意是有向邊）

參考代碼：

#include 
#include 
#include 
#include 
using namespace std;

const int MAXN = 1010;
const int MAXM = 2010;
const int INF = 0x3f3f3f3f;

struct Edge {
    int u, v, cost;
} edge[MAXM];
int nCase, cCase, n, m, dis[MAXN];
bool visited[MAXN], dp[MAXN];
vector G[MAXN];

bool dfs(int n) {
    if (n == 0) return true;
    if (visited[n]) return dp[n];
    visited[n] = true;

    for (int i = 0; i < G[n].size(); i++) {
        if (dfs(G[n][i])) {
            return dp[n] = true;
        }
    }
    return dp[n] = false;
}

bool Bellman_Ford() {
    for (int i = 0; i < n; i++) {
        dis[i] = (i == 0 ? 0 : INF);
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < m; j++) {
            if (dis[edge[j].v] > dis[edge[j].u] + edge[j].cost) {
                dis[edge[j].v] = dis[edge[j].u] + edge[j].cost;
            }
        }
    }
    for (int i = 0; i < m; i++) {
        if (dis[edge[i].v] > dis[edge[i].u] + edge[i].cost) {
            if (dfs(edge[i].u)) return false;
        }
    }
    return true;
}

void init() {
    memset(visited, false, sizeof(visited));
    memset(dp, false, sizeof(dp));
    dp[0] = visited[0] = true;
    for (int i = 0; i < MAXN; i++) {
        G[i].clear();
    }
}

void input() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].cost);
        G[edge[i].u].push_back(edge[i].v);
    }
}

void solve() {
    if (!Bellman_Ford()) {
        printf("Case #%d: possible\n", ++cCase);
    } else {
        printf("Case #%d: not possible\n", ++cCase);
    }
}

int main() {
    scanf("%d", &nCase);
    while (nCase--) {
        init();
        input();
        solve();
    }
    return 0;
}