HDU 4034 Graph：已知最短路徑重構原圖最少邊數（Floyd 逆向思維）

題目大意

給定有向圖任意兩點間的最短路徑長度，求原圖可能的最少邊數。若無合法圖輸出 impossible。N ≤ 100。

核心觀察

若最短路徑矩陣 dist[i][j] 滿足三角不等式 dist[i][j] ≤ dist[i][k] + dist[k][j]，且對於某對 (i,j) 存在 k 使等號成立，則邊 (i,j) 可被省略（因路徑 i→k→j 已達到最短）。

算法步驟

1. 檢查矩陣合法性：若存在 dist[i][j] > dist[i][k] + dist[k][j] 則 impossible。
2. 初始邊數為所有非零 dist[i][j] 的個數（有向圖）。
3. 對每個三元組 (i,j,k)，若 dist[i][j] == dist[i][k] + dist[k][j] 且 k ≠ i,j，則邊 (i,j) 可刪減，計數器減一並 break（避免重複刪減）。

代碼實現

int Search() {
    int flag = 1, ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) if (i != j)
            for (int k = 1; k <= n; ++k) if (k != i && k != j) {
                if (Map[i][j] > Map[i][k] + Map[k][j]) return -1; // 不合法
                if (Map[i][j] == Map[i][k] + Map[k][j]) { ans++; break; } // 可省略
            }
    return ans;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas) {
        scanf("%d", &n);
        int totalEdges = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j) {
                scanf("%d", &Map[i][j]);
                if (Map[i][j]) totalEdges++;
            }
        int reducible = Search();
        printf("Case %d: ", cas);
        if (reducible == -1) puts("impossible");
        else printf("%d\n", totalEdges - reducible);
    }
}

複雜度

三重循環 O(N³)，N=100 時 10⁶ 操作，極快。