UVa10805 - Cockroach Escape Networks(Floyd)

題目大意

蟑螂們住在 Bill 的房間哩，這個房間有很多蟑螂的洞穴與小徑，但 Bill 開燈後蟑螂們會四處逃串到其他的洞穴裡面，當最後一隻蟑螂抵達到他的目的地時稱之為緊急回應時間，(不理解題目原意可以想成從洞穴 A 經過 洞穴 B 到洞穴 C 的緊急時間，個人看的也不是很確定)，請輸出緊急回應時間是多少。
EX: 所有的蟑螂到他想要的目的地都會走最短路徑

題目連結

重點觀念

• 演算法知識 - Floyd-Warshall algorithm (無權重、有權重向圖)
• 不一定在中間

分析

• 由於題目沒有說從哪個點出發，因此我們主要想法就是對所有點做 floyd，並找出最小最大距離。但如果只有這樣想還不會 AC。
• 因為題目沒有說從哪個點出發，也就表示其實也可以從洞穴與洞穴之間出發也可以。
  • 在最遠距離是偶數時不會受到影響，一定都還是從洞穴出發
  • 但如果最遠距離是奇數時，就不一定都是從洞穴出發，其實也可以從洞穴與洞穴之間出發也可以。
• 因此要加入虛邊，讓洞穴與洞穴之間再增加一個虛擬洞穴，來考慮最遠距離是奇數的問題。

心得

這一題的英文可以再寫得更好一些，讓我看懂，不然他的英文真的非常不優秀…、不好理解。

參考連結

Cockroach Escape Networks by Morris
(UVA) 10805 - Cockroach Escape Networks

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL

using namespace std;
const int INF = 1e9 + 7;
const int MAXN = 510;
int t, kase=1;
int n, m;
int a, b;
int dp[MAXN][MAXN];

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i = 0; i < MAXN; i++){
            for(int j = 0; j < MAXN; j++){
                dp[i][j] = INF;
            }
            dp[i][i] = 0;
        }
        int nodes = n;
        for(int i = 0; i < m; i++){ //分析 3，加入虛邊 node
            cin >> a >> b;
            //cout << "a b nodes " << a << " " << b << " " << nodes << "\n";
            dp[a][nodes] = dp[nodes][a] = 1;
            dp[b][nodes] = dp[nodes][b] = 1;
            nodes++;
        }
        //cout << "nodes " << nodes << "\n";
        for(int k = 0; k < nodes; k++){ //floyd
            for(int i = 0; i < nodes; i++){
                for(int j = 0; j < nodes; j++){
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                    //cout << "i j dp " << i << " " << j << " " << dp[i][j] << "\n";
                }
            }
        }

//        for(int i = 0; i < nodes; i++){
//            for(int j = 0; j < nodes; j++){
//                cout << dp[i][j] << " ";
//            }
//            cout << "\n";
//        }

        int ans = INF;
        for(int i = 0; i < nodes; i++){ //尋找最小最遠距離
            sort(dp[i] , dp[i] + n);
            //cout << "max1 max2 " << dp[i][n-1] << " " << dp[i][n-2] << "\n";
            //ans = min(ans, dp[i][n-1] +  dp[i][n-2]);
            ans = min(ans, dp[i][n-1]);
        }
        //ans /= 2;
        cout << "Case #" << kase++ << ":\n";
        cout << ans << "\n\n";

    }

    return 0;
}