UVa11742 - Social Constraints (數論 Math theorm、暴力搜尋 Brute force)

題目大意

青少年的社交是件很麻煩的事情，每個人都有喜歡與不喜歡的人，喜歡的人要坐在一起、不熟的人要分開坐、討厭的人要坐在對邊，給你 n 個人，m 個表示 x 與 y 要相隔 c 個位置。請輸出所有的可能性

其中 \(n \leq 8\)、\(0 \leq m \leq 20\)

題目連結

重點觀念

• 暴力搜尋
• 時間複雜度的確定
• 了解符合題目的規定即可，在題目可以允許的範圍內再好的演算法都一樣

分析

出了這題，讓我覺得我不會寫程式…，我一開始是想要把全部的排列組合進行優化在來解，但卻發現這題有點太難…。

我們可以得知 \(8! = 40320\)，用暴力解的複雜度才這麼大，肯定可以暴力解八XDD。
後來查詢網路上後得知，只需要暴力，最後在檢查是否有符合規定，就可以。

參考連結

UVa 11742 - Social Constraints by 小白菜又菜

心得

可惡RRRR，原本這題應該對我來說很簡單R，怎麼會解不出來呢QQ。

現在慢慢了解到時間複雜度的重要性，並不是想要把全部都做到最好，而是只要符合題目的要求就好，不需要自己拿劍逼自己做到最好。

但我們只是根據題目進行分析，如果以後有比這時間複雜度更嚴格的題目，理所當然的需要更好的程式碼。

題目程式碼

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

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 10;
int n, m, a, b, c;
int peoples[MAXN]; //index 是人們，value 是座位
int position[MAXN]; //index 是座位，value 是判斷此位置是否有被占用
int cnt = 0; //計算答案

struct relation{ 
    int x,y,v;
    relation(){}
    relation(int _x, int _y, int _v){
        x = _x;
        y = _y;
        v = _v;
    }
};
vector<relation > listed; //紀錄 m 個關係

int islegal(relation concern){ //判斷位置是否有合法
    if(concern.v < 0){ //由於是至少要隔 c 個位置，所以是大於等於
        return abs(peoples[concern.x] - peoples[concern.y]) >= abs(concern.v);
    }
    else if(concern.v >= 0){ //由於是要彼此坐在 c 個位置內，所以是小於等於
        return abs(peoples[concern.x] - peoples[concern.y]) <= concern.v;
    }
}

void dfs(int people){ //排列組合
    //cout << "people " << people << '\n';
    if(people >= n){ //這次的排列組合完成後
        for(int i = 0; i < listed.size(); i++){ //判斷有沒有都符合 m 個條件
            if(!islegal(listed[i])) return; //不符合就 return
        }
        cnt++; //有符合就紀錄
        return;
    }
    for(int i = 0; i < n; i++){ //排列組合核心
        if(position[i]) continue; //如果這位置有被坐到就換下個
        peoples[people] = i; //紀錄人的位置
        position[i] = 1; //紀錄位置是否有被占用
        dfs(people+1); //進行 dfs
        position[i] = 0; //此位置不再被坐
    }
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    while(cin >> n >> m && (n+m) != 0){ //輸入資料
        listed.clear(); //清除 m 個條件
        for(int i = 0; i < m; i++){ //輸入 m 個條件
            cin >> a >> b >> c;
            relation temp(a,b,c);
            listed.push_back(temp);
        }
        for(int i = 0; i < n; i++){ //清空資料
            position[i] = 0;
            peoples[i] = 0;
        }
        cnt = 0;
        dfs(0); //進行排列組合
        cout << cnt << '\n'; //輸出答案
    }

    return 0;
}