ProblemK Assigning Frequencies (暴力搜尋 Brute force)

題目大意：

給你一張圖，這圖不會超過 25 個 Node，試問能不能用 3 個顏色塗滿所有點但相鄰的點不能有相同顏色。
題目提示: 測資不會超過 85 筆。

分析：

如果對暴力搜尋法有一定了解的人，應該看到題目就會馬上想到暴力搜尋法了吧！
可惜我不是，我用了一個奇怪的想法然後還沒解開…。(有興趣的可以往下滑)

甚麼時機該用暴力搜尋法？

1. 題目有告訴你測資不超過幾筆，但那數字卻不大
2. 圖也不大，相較於其他圖論的題目
3. 明顯看到他的測資基本上不大於 100 or 1000，應題目而定

由於是暴力搜尋法，也沒有甚麼好講，但他有一地方神奇就在於遞迴。讓我來稍微解說下:

依序新增一點，然後塗色

這是我認為最為有趣的地方，也是最困擾我的地方。一開始我認為這遞迴非常好寫，輕輕鬆鬆，開始寫以後才證明我錯了，在這邊呼籲各位不要精神 AC 阿，真的，魔鬼藏在細節裡。

由於他依序新增一點，所以她其實在過程中，並不是完整的圖而是分裂的，但沒關係。不影響我們作答，因為之後連起來時就會發現顏色一樣而再將點更改顏色。如果都不行就可以直接 FALSE。

塗色，你是要幫下一個點選色。這是遞迴裡面最有魅力的地方，明明是 a 的遞迴 time，但卻幫 b 做好顏色選擇。你可能會覺得很奇怪？
但你仔細想想，如果不這樣做的話，那你在 a 的遞迴才幫 a 做塗色，那複雜度雖然一樣，但程式碼就非常亂了，因為要考慮你是因為 3 個顏色都不行呢？還是這顏色可以通過。這兩種情況下，你可能還需要一個 flag 之類的東西來判斷，不好看。太醜了。
但這點我也是觀看別人程式碼，我才懂得。寫這份文件的人果真大神。

參考連結

我在解這題時，是閱讀觀看這位大神才得以解出的，謝謝他。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 30
using namespace std;
int path[MAXN][MAXN] = {} ;
int node[MAXN] = {} ;
int n , p , N ;

int DFS(int v){
    for(int i = 0 ; i < v ; i++){
        if(path[v][i] && node[v] == node[i])
            return false ;
    }

    if(n == v-1)
        return true ;

    for(int j = 0 ; j < 3 ; j++){
        node[v+1] = j ;
        if(DFS(v+1))
            return true ;
    }
    return false ;

}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    int _i , _j ;
    cin >> N ;
    while(N--){
        cin >> n >> p ;
        //clear
        for(int i = 0 ; i < n ; i++){
            for(int j = 0 ; j < n ; j++)
                path[i][j] = 0 ;
        }

        for(int i = 0 ; i < p ; i++ ){
            cin >> _i >> _j ;
            path[_i][_j] = 1 ;
            path[_j][_i] = 1 ;
        }
        if(DFS(0))
            cout << "Y" ;
        else
            cout << "N" ;
        cout << '\n' ;
    }
    return 0;
}

我再看到此題的想法:

這裡是廢文。如果不想要了解我的想法可以直接略過，因為我的想法是錯誤的。但如果想看看我的思考邏輯就建議看看。

我一開始看到這題目時，就想到簡單 2 顏色塗色問題，想說直接用 BFS，搞定！但絕對沒有那麼簡單啊 XD，於是我就想出一方法關於我要怎麼解出這題目。
怎麼做呢，用有點類似於 DP 的方式，開一 struct，裡面放入一陣列代表有 3 顏色，只要他相鄰的點有被用過的顏色，那此點就不能用這顏色，只要附近的點都將 3 種顏色都用過就輸出 N，是不是覺得我的想法還不賴！當初的我也覺得我的想法很不錯，所以就用了這方式。

寫出來後，丟去 judge，卻發現是錯的！可是錯在哪裡我不知道…，非常討厭。於是我就去問了我的朋友們，但我的朋友們似乎也不太清楚，於是就問了奧林匹亞銅牌國手，他說出了一句令我震驚的話。

原來剛剛的我試圖在嘗試不可能的任務阿，怕。差點我就能把 3 塗色問題的演算法名稱掛上大衛了www，沒，開玩笑的。於是我就也放棄了此題，使用暴力搜尋法 ಥ⌣ಥ。

下面是我寫的程式碼(我的想法)，有興趣的可以拿去研究看看www。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
vector<int> path[30] ;
deque<int> nodes ;

int N , n , p  ;

struct Node{
    int color[3] = {} ;
    int use = 0 ;
    void clear(){
        color[0] = 0 ;
        color[1] = 0 ;
        color[2] = 0 ;
        use = 0 ;
    }

}node[30];

int choose(int i , int k ){
    for(int j = 0 ; j < path[i].size() ; j++){
        if(!node[path[i][j]].use){
            nodes.push_back(path[i][j]);
            node[path[i][j]].use = 1 ;
        }

        if(node[path[i][j]].color[k])
            return 0 ;
    }
    return 1 ;
}

int check(int i ){
    for(int k = 0 ; k < 3 ; k++){
        if(node[i].color[k])
            continue ;
        if(choose(i,k)){
            node[i].color[k] = 1 ;
            return 1 ;
        }
    }
    return 0 ;
}

int BFS(){
    //node[0].color[0] = 1 ;
    nodes.push_back(0) ;
    node[0].use = 1 ;
    while(nodes.size()){
        if(!check(nodes.front()))
            return 0 ;
        nodes.pop_front();
    }
    return 1 ;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt" , "r" , stdin );
#endif // LOCAL
    int i , j ;
    cin >> N ;
    while(N--){
        cin >> n >> p ;

        //clear
        for(int i = 0 ; i < n ; i++){
            path[i].clear() ;
            node[i].clear() ;
        }
        nodes.clear() ;

        //bulid
        for(int k = 0 ; k < p ; k++){
            cin >> i >> j ;
            path[i].push_back(j) ;
            path[j].push_back(i) ;
        }

        if(BFS())
            cout << "Y" ;
        else
            cout << "N" ;
        cout << '\n' ;

        /*//debug
        for(int i = 0 ; i < n ; i++){
            cout << i << ' ' << node[i].color[0] << ' ' << node[i].color[1] << ' ' << node[i].color[2] << '\n' ;
        }
        */

    }
    return 0;
}