UVa10660 - Citizen attention offices (暴力搜尋 Brute force)

題目大意

有一個正方形的城市，被分隔成 25 個區域，size 是 5 * 5，每個區域都有住著許多人，政府要在裡面設 5 個行政據點，其目標是可以幫助此城市所有人都可以透過直走與橫走的方式走到行政據點(其中一個就可以)，且讓都市中的所有人總和走起來距離最短。

題目連結

重點觀念

• 寫出時間複雜度
• 進行思考，是否有非暴力搜尋的方式可以解出此題
• 能夠閱讀題目

分析

這題是一個很麻煩的題目…，通常我看到這種題目我都會認為一定有一種規律可行、可解。

結果這題我想了很久後，還是想不太出來，查了查詳解後才知道這題應該直接用暴力破解的方式將她解出，由於 DFS 的時間複雜度是 \(O(n^m)\)，n 是邊數、m 是深度，而這裡的最大時間複雜度應該是 \(25^5 = 9765625\)，在時間複雜度低於 2000 萬以內，基本上一個良好的 OJ 都能夠順利解開，因此我們就直接使用 DFS。

怎麼做呢?

作法很簡單，不斷進行 DFS，必且深度搜尋，當深度抵達 5 時，判斷城市中所有 area 到行政據點的最短距離乘上人口數量，找出最小值，就是我們要的答案。

需要注意的是，那個區域只需要找到一個行政據點距離最小就好，我這邊還卡了一下..。

參考連結

UVa 10660 - Citizen attention offices by 小白菜又菜
深度優先搜尋 by Wiki

心得

習慣性看到這種題目就是要找規律，然後找到可以優化的點進行優化，就能輕鬆解出。雖然大部分時間都找不出來優化點….QQ。我不夠聰明RRR。

經過了這題後，稍微沒有那麼思考僵化了，其實有的時候一直過度寫同樣題目容易造成自己的思考模式都往同個部分思考，現在有寫過這題後對於思考方式又更發散了一些。雖然說太發散找不到方向，但是不發散絕對找不到正確答案。

總之，希望自己 ICPC 可以得到銀獎，拜託了。

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 30 //題目最大區域量，保險起見開更大
using namespace std;
int num[MAXN], ans[MAXN], result[MAXN];
//num 題目的區域，ans 我們要輸出的答案，result 當前 DFS 中每個區域到行政據點最短距離的總和
//ans, result 只會用到前 5 個陣列值
int t, n, a, b, c; //輸入資料用
int d = MAXN*MAXN*1000; //理論上每個區域到行政據點最大距離不超過此值，因為人口最多只有 1000
//因此 25個區域*最大距離25(不可能達到)*人口數量，可以當作此題的最大值

void dfs(int p, int office){
    if(office >= 5){ //如果建立了 5 個辦公室，就開始找每個區域到行政據點最短距離的總和
        int sum = 0; //當前 DFS 每個區域到行政據點最短距離的總和
        //cout << "result " << result[i] << '\n';
        for(int j = 0; j < 25; j++){ //遍地每個區域
            int compute = MAXN*MAXN*1000, temp; 
            for(int i = 0; i < 5; i++){ //判斷哪個行政據點離當前區域最短
                temp = num[j] * (abs(result[i]/5 - j/5) + abs(result[i]%5 - j%5));
                compute = min(temp, compute); //取最小的
            }
            sum += compute; //加到 sum
        }

        //定義: A = 每個區域到行政據點最短距離的總和
        if(sum < d){ //如果當前的 A 比過去中最小的 A，還小就取代
            //cout << "test:" << sum << ' ';
            d = sum; //將答案值替換
            for(int i = 0; i < 5; i++){ //將答案值替換
                ans[i] = result[i];
                //cout << result[i] << ' ';
            }
            //cout << '\n';
        }
        return;
    }
    for(int i = p+1; i < 25; i++){ //不斷進行 DFS，做所有的排列組合
        result[office] = i; //當前的第 office 的辦公室為 i 區域 
        dfs(i, office+1); //往下一層邁進，題目有說明輸出要遞增，因此 i 必須是 p+1，否則會重覆到
    }
}

void debug(){ //debug 用
    for(int i = 0; i < 5; i++){
        for(int j = 0; j < 5; j++)
            cout << num[i*5+j] << ' ';
    cout << '\n';
    }
}


int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n;
        memset(num, 0, sizeof(num)); //清空，以免干擾這次資料
        while(n--){ //輸入資料
            cin >> a >> b >> c;
            num[a*5+b] = c;
        }
        //debug();
        d = MAXN*MAXN*1000;
        dfs(-1, 0); //一開始是 -1 是因為，我們的 DFS 排列組合迴圈是 p+1

        cout << ans[0];
        for(int i = 1; i < 5; i++) cout << ' ' << ans[i]; //輸出答案
        cout << '\n';
    }
    return 0;
}