題目 Problem#
題目連結：https://zerojudge.tw/ShowProblem?problemid=e880
敘述 Description#
酷酷鯊是一支新成立的棒球隊，共有 $N$ 位球員。球隊裡原本氣氛融洽，大家都是好麻吉，同心協力爭取年度總冠軍。然而，最近一連串的比賽不順利，球員間開始出現摩擦。今天，棒球聯盟邀請了總統夫人到場開球。總統夫人是酷酷鯊隊的球迷，因此她希望能和全體球員合影留念。拍照時，球員們會站成一列。為了避免尷尬，球隊經理希望在安排拍照的隊型時，不要讓彼此有和芥蒂的球員站在一起。
舉例來說，如果有五位球員 A, B, C, D, E，其中 A 和 B 不願意站在一起，C 和 D 不願意站在一起，那麼 ABCDE 和 ABCED 不是適當的隊型，而 ACBDE 和 CADEB 則都是適當的隊型。
現在請你撰寫一個程式，協助球隊經理在總統夫人落臨之前，排出一個適當的合影隊型吧!
輸入 Input#
第一行為球員人數 $N$，$N \leq 15$。（球員代號從 A 開始編起。）
第二行為有摩擦的球員配對數 $M$，$M \leq 50$。
第三行開始，每一行有兩個字元，代表有摩擦的兩個球員代號。兩個字元間以一個空格隔開。
輸出 Output#
請輸出以字典遞增排序方式的第一個適合隊型。如果沒有任何適合隊型，請輸出 No Solution。計算時間不得超過2秒鐘。
範例輸入 Sample Input#
範例1:
5
2
A B
C D
範例2:
4
4
A B
C D
C A
C B範例輸出 Sample Output#
範例1:
ACBDE
範例2:
No Solution提示 Hint#
題解 Solution#
熟悉 STL 一定知道 next_permutation 可以直接窮舉 但是，直接窮舉 $15! = 1307674368000$ 種可能，沒辦法在 2 秒跑完（ZJ 直接開 1 秒） 必定要自己寫 DFS 剪枝了
用個 $15 \times 15$ 的矩陣紀錄他們能不能站在一起 DFS 時候 當前的成員 跟 前一個被選的成員，查詢能不能站在一起 可以就往下尋找，不能就可以直接找下一位成員
程式碼 Accepted Code#
/*
Author: Jerry Yang C.H. (tico88612)
Date: 2020/2/4
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<double,double> pdd;
#define SQ(i) ((i)*(i))
#define MEM(a, b) memset(a, (b), sizeof(a))
#define SZ(i) int(i.size())
#define FOR(i, j, k, in) for (int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for (int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define REP1(i,j) FOR(i, 1, j+1, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define ALL(_a) _a.begin(),_a.end()
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define X first
#define Y second
#ifdef tmd
#define debug(...) do{\
fprintf(stderr,"%s - %d (%s) = ",__PRETTY_FUNCTION__,__LINE__,#__VA_ARGS__);\
_do(__VA_ARGS__);\
}while(0)
template<typename T>void _do(T &&_x){cerr<<_x<<endl;}
template<typename T,typename ...S> void _do(T &&_x,S &&..._t){cerr<<_x<<" ,";_do(_t...);}
template<typename _a,typename _b> ostream& operator << (ostream &_s,const pair<_a,_b> &_p){return _s<<"("<<_p.X<<","<<_p.Y<<")";}
template<typename It> ostream& _OUTC(ostream &_s,It _ita,It _itb)
{
_s<<"{";
for(It _it=_ita;_it!=_itb;_it++)
{
_s<<(_it==_ita?"":",")<<*_it;
}
_s<<"}";
return _s;
}
template<typename _a> ostream &operator << (ostream &_s,vector<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,set<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a> ostream &operator << (ostream &_s,deque<_a> &_c){return _OUTC(_s,ALL(_c));}
template<typename _a,typename _b> ostream &operator << (ostream &_s,map<_a,_b> &_c){return _OUTC(_s,ALL(_c));}
template<typename _t> void pary(_t _a,_t _b){_OUTC(cerr,_a,_b);cerr<<endl;}
#define IOS()
#else
#define debug(...)
#define pary(...)
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
#endif
const ll MOD = 1000000007LL;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
const int iNF = 0x3f3f3f3f;
// const ll MAXN =
int N, M;
bool non[16][16] = {0};
bool judge = false;
bool visited[16] = {0};
void dfs(int now, string ans){
if(now == N){
cout << ans << '\n';
judge = 1;
return;
}
for(int i = 0; i < N && !judge; i++){
if(!visited[i] && now && !non[ans[now - 1] - 'A'][i]){
visited[i] = 1;
string tmp = ans + (char)(i + 'A');
dfs(now + 1, tmp);
visited[i] = 0;
}
else if(!visited[i] && now == 0){
visited[i] = 1;
string tmp = ans + (char)(i + 'A');
dfs(now + 1, tmp);
visited[i] = 0;
}
}
}
/********** Good Luck :) **********/
int main()
{
IOS();
cin >> N >> M;
while(M--){
string aa, bb;
cin >> aa >> bb;
int a = aa[0] - 'A';
int b = bb[0] - 'A';
non[a][b] = non[b][a] = 1;
}
dfs(0, "");
if(!judge)
cout << "No Solution" << '\n';
return 0;
}後記 Afterword#
一開始寫完以為會被 TLE，沒想到是直接 AC 然後交大程式寒訓因為武漢肺炎停辦 QAQ
之後再來寫一篇文，有關交大程式寒訓默哀文