UVa10987 - AntiFloyd(Floyd)

題目大意

一個系統管理師要管理一家公司的網路，他測試每一個 cable to 每一台電腦，現在他想要移除一些 cable，但不可以讓原本的速度變快或變慢，還是必須是速度一樣快的狀態。
請問他應該保留那一些電纜，如果沒有辦法移除，那就輸出 ‘Need better measurements.’

題目連結

重點觀念

• 演算法知識 - Floyd-Warshall algorithm (無權重、有權重向圖) by 大衛的筆記
• 判斷現在的電纜會不會有最短邊

分析

• 使用 floyd 檢查 path[i][j] <= path[i][k] + path[k][j]，如果有的話就表示可能會讓速度更快，沒辦法移除，直接輸出 ‘Need better measurements.’
• 如果剛好 path[i][j] == path[i][k] + path[k][j]，則表示此邊可以移除，因為可以讓 i 走 k 走 j
• 一開始先假設所有的邊都可以用，然後符合第二點的移除。

參考連結

UVa 10987 - Antifloyd by morris

題目程式碼

有一些程式碼註解在 演算法知識 - Floyd-Warshall algorithm (無權重、有權重向圖) by 大衛的筆記 請供參考。

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
//#define LOCAL
#define int long long
#define MAXN 120
using namespace std;
int kase = 1;
int path[MAXN][MAXN], edge[MAXN][MAXN];
int t, n;

int anti_floyd(){
    for(int k = 1; k <= n; k++){ //floyd
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(path[i][j] > path[i][k] + path[k][j]){ //分析 1
                    cout << "Need better measurements.\n";
                    return 0;
                }
                if(i == j || j == k || i == k) continue; //同樣的點，沒有意義
                if(path[i][j] == path[i][k] + path[k][j]){ //分析 2
                    //cout << "i j k " << i << " " << j << " " << k << "\n";
                    edge[i][j] = 0;
                }
            }
        }
    }

    int cnt = 0; //記錄有多少邊被留下來
    for(int i = 1; i <= n; i++){
        for(int j = 1; j < i; j++){
            if(edge[i][j]) cnt++;
        }
    }

    cout << cnt << "\n"; //輸出所有邊
    for(int i = 1; i <= n; i++){
        for(int j = i+1; j <= n; j++){
            if(edge[i][j]) cout << i << " " << j << " " << path[i][j] << "\n";
        }
    }

    /* print
    cout << "\n";
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cout << edge[i][j] << " ";
        }
        cout << "\n";
    }
    cout << "\n";
    */
    return 1;

}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        for(int i = 1; i <= n; i++){ //分析第三點
            for(int j = 1; j <= n; j++){
                edge[i][j] = 1;
            }
        }

        int cost;
        for(int i = 1; i <= n; i++){ //輸入資料
            for(int j = 1; j < i; j++){
                cin >> cost;
                path[i][j] = cost;
                path[j][i] = cost;
            }
            path[i][i] = 0;
        }
        cout << "Case #" << kase++ << ":\n";
        anti_floyd();
        cout << "\n";

    }
    return 0;
}