Board logo

標題: 202409潛力2-校外教學分組libra [打印本頁]
作者: may    時間: 2024-10-20 15:49     標題: 202409潛力2-校外教學分組libra

[attach]20107[/attach]
校外教學分組 (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    時間: 2024-10-20 20:36

  1. #include <bits/stdc++.h>
  2. using namespace std;

  4. const int maxn = 16 + 1;
  5. const int maxm = maxn * (maxn - 1) / 2;
  6. const int inf = 2147483647;

  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. }

  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. }

  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. }
複製代碼
作者: may    時間: 2024-12-18 22:24

  1. //#include <iostream>
  2. //#include <vector>
  3. //#include <algorithm>
  4. //#include <cmath>
  5. #include <bits/stdc++.h>
  6. using namespace std;

  8. // 用來檢查一組學生是否存在朋友關係（違規組合）
  9. bool isValidGroup(const vector<int>& group, const vector<vector<bool>>& friends) {
  10.     for (int i = 0; i < group.size(); i++) {
  11.         for (int j = i + 1; j < group.size(); j++) {
  12.             if (friends[group[i]][group[j]]) {
  13.                 return false; // 存在朋友關係，組合不合法
  14.             }
  15.         }
  16.     }
  17.     return true;
  18. }

  20. // 遞迴分組的核心函數
  21. void divideGroups(int student, vector<vector<int>>& groups, const vector<vector<bool>>& friends, int& minDifference, int N) {
  22.     if (student > N) { // 所有學生都已分組
  23.         int maxSize = 0, minSize = N;
  24.         for (const auto& group : groups) {
  25.             maxSize = max(maxSize, (int)group.size());
  26.             minSize = min(minSize, (int)group.size());
  27.         }
  28.         minDifference = min(minDifference, maxSize - minSize);
  29.         return;
  30.     }

  32.     for (auto& group : groups) {
  33.         group.push_back(student); // 嘗試將當前學生加入該組
  34.         if (isValidGroup(group, friends)) {
  35.             divideGroups(student + 1, groups, friends, minDifference, N); // 遞迴分配下一位學生
  36.         }
  37.         group.pop_back(); // 回溯
  38.     }
  39. }

  41. int main() {
  42.     int N, M;
  43.     cin >> N >> M;

  45.     vector<vector<bool>> friends(N + 1, vector<bool>(N + 1, false));

  47.     // 讀取朋友關係
  48.     for (int i = 0; i < M; i++) {
  49.         int X, Y;
  50.         cin >> X >> Y;
  51.         friends[X][Y] = friends[Y][X] = true;
  52.     }

  54.     // 初始化三組
  55.     vector<vector<int>> groups(3);

  57.     int minDifference = N; // 設置為最大可能值
  58.     divideGroups(1, groups, friends, minDifference, N);

  60.     // 如果無法找到合法分組，minDifference 不會被更新
  61.     if (minDifference == N) {
  62.         cout << -1 << endl;
  63.     } else {
  64.         cout << minDifference << endl;
  65.     }

  67.     return 0;
  68. }
  69. /*
  70. 5 5
  71. 1 2
  72. 2 3
  73. 3 4
  74. 4 5
  75. 1 5
  76. */
複製代碼
----------------------------------------------------
程式邏輯解釋
輸入處理與資料結構設置：

使用 friends 矩陣記錄朋友關係，friends[j] = true 表示學生 i 和 j 是朋友。
使用三個向量的 groups 表示分成的三組學生。
核心檢查函數 isValidGroup：

檢查某組內是否有任意兩位學生是朋友。
如果有朋友關係，則該組不合法。
分組遞迴邏輯 divideGroups：

對每位學生嘗試加入三個組中的一個。
如果當前組合合法，則遞迴處理下一位學生。
如果全部學生分組完成，計算三組最大與最小人數的差值，並更新最小差值。
結果輸出：

如果分組後的最小差值未被更新，表示無法找到合法分組，輸出 -1。
否則輸出最小差值。
輸入與輸出範例解析
範例1：
輸入：

複製程式碼
5 5
1 2
2 3
3 4
4 5
1 5
輸出：

複製程式碼
1
解釋： 分組為 [1, 4], [2, 5], [3]，最大人數為 2，最小人數為 1，差值為 1。

範例2：
輸入：

複製程式碼
4 6
1 2
1 3
1 4
2 3
2 4
3 4
輸出：

diff
複製程式碼
-1
解釋： 無法找到合法分組，因為所有學生彼此都是朋友。

範例3：
輸入：

複製程式碼
6 1
1 2
輸出：

複製程式碼
0
解釋： 分組為 [1, 2], [], [] 或其他方式，最大與最小人數的差值為 0。

這段程式碼適合解決此問題並兼具清晰的邏輯與效率。
-------------------------------------------------------------------------------
size_t j = i + 1 是 C++ 程式碼中的一部分，定義了一個無符號整數型別變數 j，並將它初始化為 i + 1 的值。

詳細解釋
size_t:
這是一種無符號整數型別，通常用於表示非負數的大小或索引值。
它的具體大小（位元數）依據作業系統和編譯器而定，通常是 32 位或 64 位。
使用 size_t 可以避免索引或大小計算中出現負數的情況。
j = i + 1:
表示將變數 j 的值設置為變數 i 的值加 1。
在上下文中，這是用來遍歷 group 中的每個元素時，確保 j 起始於 i 的下一個位置，避免重複檢查自己。
背景功能
在這段程式碼中，for (size_t j = i + 1; j < group.size(); ++j) 是一個內層迴圈，用來檢查組內的任意兩位學生是否有朋友關係。起始值 i + 1 確保只檢查 i 之後的學生，避免冗餘的檢查（如檢查 friends[group][group[j]] 和 friends[group[j]][group] 是重複的）。



在程式碼中，for (auto& group : groups) 是一個範圍式 for 迴圈（C++11 引入的語法），其作用是逐一遍歷容器 groups 中的每個元素。

詳細解釋
關鍵詞 auto&：

auto：讓編譯器自動推斷變數 group 的型別，根據 groups 的元素型別推斷出 group 是 vector<int>&（一個整數向量的參考）。
&：使用參考，允許直接修改 groups 中的每個子向量，而不需要複製。
groups 容器：

groups 是一個包含三個向量的容器，類型為 vector<vector<int>>，每個向量表示一組學生的編號。
作用：

這段程式碼的目的，是將當前的學生嘗試加入三個組中的某一組。
由於 group 是參考，對 group 的修改會直接影響到 groups 容器內的對應子向量。
範例
假設：

vector<vector<int>> groups = {{1}, {2}, {3}};
範圍式 for 的運行如下：

第一次迴圈：group 參考 groups[0]（內容為 {1}）。
第二次迴圈：group 參考 groups[1]（內容為 {2}）。
第三次迴圈：group 參考 groups[2]（內容為 {3}）。
對 group 的操作會直接改變 groups 對應的內容。

程式片段意圖
該迴圈在遞迴過程中逐一嘗試將學生加入每個組，並利用參考特性避免不必要的複製操作，提升程式效能。
-------------------------------------------------------------------
為什麼N要+1
N + 1 是用於初始化 friends 二維矩陣的大小，其中 N 是學生的數量。以下是為什麼需要加 1 的詳細解釋：
背景
在程式中，friends 是一個二維布林矩陣，用來記錄學生之間的朋友關係。大小為 (N + 1) x (N + 1)，每個元素 friends[X][Y] 表示學生 X 和學生 Y 是否是朋友。

為什麼要加 1
學生編號從 1 開始：

題目中提到，學生的編號是從 1 到 N。
為了方便直接使用學生編號作為矩陣的索引，矩陣需要有 N + 1 行和列。
例如，對於 5 位學生，矩陣索引會是 0 到 5。其中索引 0 不使用，而索引 1 到 5 對應學生。
避免偏移計算：

如果矩陣大小僅為 N x N，則需要將學生編號減 1（例如 friends[X-1][Y-1]）來進行索引操作，這樣會增加程式的複雜性。
增加矩陣的大小到 N + 1 後，可以直接使用學生編號（如 friends[X][Y]）而不需要額外的轉換。
結論
將矩陣大小設定為 N + 1 是為了讓程式碼更簡潔、直觀，並且符合題目中學生編號從 1 開始的設定。如果有其他問題，歡迎進一步詢問！
-------------------------------------------------------------

解釋 group.pop_back();
這一行程式碼的作用是回溯，用來撤銷前面的一次狀態改變，讓程式可以嘗試其他可能的分組方式。

背景
在遞迴函數 divideGroups 中，我們使用以下邏輯來嘗試分組：

加入學生：利用 group.push_back(student)，將當前學生加入某一組。
檢查組合合法性：透過 isValidGroup 函數檢查組內是否有違規（存在朋友）。
進入下一層遞迴：若組合合法，遞迴處理下一位學生。
回溯：用 group.pop_back()，將學生從該組移除，恢復組的原始狀態，然後嘗試將學生加入其他組。
回溯的必要性
避免重複狀態：每次嘗試不同分組時，都需要恢復原本的狀態，否則後續嘗試會受到之前選擇的影響。
完整探索所有可能解：回溯機制允許程式依序探索所有可能的分組情況，以找到最佳解。
範例
假設目前有 3 位學生，程式試圖將第 1 位學生加入第 1 組：

加入學生 1：group[0] = {1}。
遞迴嘗試學生 2：
將學生 2 加入第 1 組後，group[0] = {1, 2}。
發現違規（例如，學生 1 和 2 是朋友），需要回溯。
執行 pop_back()，group[0] 恢復為 {1}。
再嘗試將學生 2 加入其他組。
小結
group.pop_back(); 是遞迴與回溯算法的核心部分之一，確保每一次遞迴執行後，狀態能恢復初始，以便探索其他解決方案。如果沒有這行程式碼，分組狀態將無法正確更新，導致程式結果不正確。



歡迎光臨 種子論壇 | 高雄市資訊培育協會學員討論區 (http://istak.org.tw/seed/) Powered by Discuz! 7.2