202409潛力2-校外教學分組libra

may

校外教學分組 (Trip)
問題敘述
校外教學要將N位學生分成3組行動。老師認為如果組內有學生彼此是朋友的話可能會因為聊天導致秩序不好，因此同一組內不能存在有兩位學生彼此是朋友關係。
同時，為了使每一組的導遊負擔儘量一樣，老師也希望「最多人的組」和「最少人的組」人數的差值越小越好。
例如：有N = 5位同學，有M = 5筆學生們的朋友關係。假設學生1和2、學生2和3、學生3和4、學生4和5、學生1和5互為朋友，我們可以將學生1和4分成一組、學生2和5分成一組、學生3獨立成一組，則「最多人的組」有2 人，「最少人的組」有1人，差值為1。這是最小的差值了。
給定M筆學生間的朋友關係，請幫老師計算出分組後「最多人的組」和「最少人的組」人數的最小差值；如果無法分組，請輸出 -1。

輸入格式
第一列有兩個正整數N 與 M (3 ≤ N ≤ 16, M ≤ N×( N-1)/2)，表示有N位學生和M筆學生們的朋友關係。接下來M列，每列有兩個相異正整數 X 與 Y (1≤ X, Y ≤ N)，兩個正整數間以一個空白間隔，代表學生X和學生Y互相是朋友。輸入不存在重複的朋友關係。
輸出格式
請輸出一個整數，表示分組後「最多人的組」和「最少人的組」人數的最小差值，如果無法分組，輸出-1。
輸入範例1
5 5
1 2
2 3
3 4
4 5
1 5
輸出範例1
1
輸入範例2
4 6
1 2
1 3
1 4
2 3
2 4
3 4
輸出範例2
-1
輸入範例3
6 1
1 2
輸出範例3
0
評分說明
此題目測資分成兩組，每組測資有多筆測試資料，需答對該組所有測試資料才能獲得該組分數，各組詳細限制如下。
第一組 (20 分)：N ≤ 4。
第二組 (80 分)：無特別限制。
https://zerojudge.tw/ShowProblem?problemid=o627

may

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int maxn = 16 + 1;
   
5. const int maxm = maxn * (maxn - 1) / 2;
   
6. const int inf = 2147483647;
   
7. 
   
8. void dfs(int cur, int n, int m, int *group, const int f[maxm][2], int& ans)
   
9. {
   
10.         if (cur == n)
    
11.         {
    
12.                 bool flag = true;
    
13.                 for (int i = 0; i < m; ++i)
    
14.                 {
    
15.                         if (group[f[i][0]] == group[f[i][1]])
    
16.                         {
    
17.                                 flag = false;
    
18.                                 break;
    
19.                         }
    
20.                 }
    
21.                 if (flag == true)
    
22.                 {
    
23.                         int cnt[3] = {0};
    
24.                         for (int i = 0; i < n; ++i)
    
25.                         {
    
26.                                 ++cnt[group[i]];
    
27.                         }
    
28.                         ans = min(ans, max({cnt[0], cnt[1], cnt[2]}) - min({cnt[0], cnt[1], cnt[2]}));
    
29.                 }
    
30.                 return;
    
31.         }
    
32.         for (int i = 0; i < 3; ++i)
    
33.         {
    
34.                 group[cur] = i;
    
35.                 dfs(cur + 1, n, m, group, f, ans);
    
36.         }
    
37.         return;
    
38. }
    
39. 
    
40. int solve(int n, int m, int f[maxm][2])
    
41. {
    
42.         int group[maxn];
    
43.         int ans = inf;
    
44.         dfs(0, n, m, group, f, ans);
    
45.         if (ans == inf)
    
46.         {
    
47.                 return -1;
    
48.         }
    
49.         return ans;
    
50. }
    
51. 
    
52. int main()
    
53. {
    
54.         int n, m;
    
55.         int f[maxm][2];
    
56.         scanf("%d%d", &n, &m);
    
57.         for (int i = 0; i < m; ++i)
    
58.         {
    
59.                 scanf("%d%d", &f[i][0], &f[i][1]);
    
60.                 --f[i][0];
    
61.                 --f[i][1];
    
62.         }
    
63.         printf("%d\n", solve(n, m, f));
    
64.         return 0;
    
65. }

複製代碼