ZeroJudge 解題筆記：o627.校外教學分組 (Trip)

作者：王一哲
日期：2026年10月17日


ZeroJudge 題目連結：o627.校外教學分組 (Trip)

題目 pdf 檔連結：校外教學分組 (Trip)

解題想法

這題是TOI練習賽202409潛力組第2題，這題也很難。題目是多組測資。每組測資第1列為2個整數 $n (3 \leq n \leq 16)$、$m (m \leq n (n-1) / 2)$，代表有 $n$ 個人，編號 $1$ 到 $n$，有 $m$ 組朋友關係。接下來 $m$ 列，每列有2個相異整數 $u, v$，代表 $u, v$ 是朋友，不能不在同一組。如果要將所有人分成3組，朋友不能分在同一組，求這3組中最多人數減去最少人數的最小值。如果無法分成3組，回傳 $-1$。

由於這題的 $n$ 最大為 16，可以用二進位制的整數 $bitmask$ 代表這 $n$ 個人所有的組合，如果 $mask$ 第 $i$ 位是 $1$，代表編號 $i$ 的人在這個分組之中，但是題目的編號是從 $1$ 開始，為了配合位元運算，需要將編號改成從 $0$ 開始。解題過程主要分為 3 步：

1. 開一個長度為 $n$ 的陣列 $adj$，並用 $bitmask$ 儲存每個人的好友名單。
2. 找出所有合法的組合及人數。所有的組合數 $total = 1 << n$，開一個長度為 $total$ 的陣列 $valid$ 記錄每個組合是否合法，另一個長度為 $total$ 的陣列 $sz$ 記錄每個組合的人數。
3. 窮舉所有可能的組合，要求各組人數 $s1 \geq s2 \leq s3$，因為題目只要求分成 3 組，並沒有規定哪個組別的人數最多，加上這個條件可以少算很多狀況。

另外可以再加上一個已經找到理論最佳解的剪枝條件，如果已經找到最佳解，之後不可能再找到更好的解，可以直接輸出答案不需要再跑。如果 $n$ 是 $3$ 的倍數，可以分為人數相等的 $3$ 組，理論最佳解為 $0$；反之，理論最佳解為 $1$。在第 3 個步驟之前，可以將答案 $ans$ 定義成超出題目上限的值，例如 $1000$，如果在第 3 個步驟中沒有找到解，$ans$ 仍為預設值，代表無解，輸出 $-1$。

Python 程式碼

使用時間約為 0.5 s，記憶體約為 10.8 MB，通過測試。

def solve():
    import sys
    
    result = []
    data = sys.stdin.read().split()
    ptr = 0
    while ptr < len(data):
        n = int(data[ptr])  # n 個人
        m = int(data[ptr + 1])  # m 組關係
        ptr += 2

        # 1. 用 bitmask 儲存朋友關係
        adj = [0] * n
        for _ in range(m):
            u = int(data[ptr]) - 1  # u, v 是朋友，改成 0-index
            v = int(data[ptr + 1]) - 1
            ptr += 2
            adj[u] |= (1 << v)
            adj[v] |= (1 << u)

        # 2. 找出所有合法的組合及人數
        total = 1 << n  # 所有的組合數
        valid = [True] * total  # 組合是否合法
        sz = [0] * total  # 各組合的人數
        for mask in range(1, total):
            sz[mask] = mask.bit_count()  # 計算 mask 之中 1 的數量，就是人數
            u = (mask & -mask).bit_length() - 1  # 取 mask 的 lowbit 計算二進位制長度 - 1，即最後的 1 索引值
            prev = mask ^ (1 << u)  # 去除 u 之後的組合
            # 如果 prev 不合法，或者 mask 之中有人是 u 的朋友，mask 不合法
            if not valid[prev] or mask & adj[u]:
                valid[mask] = False

        # 3. 窮舉所有可能的組合，要求各組人數 s1 >= s2 >= s3
        ans = 1000  # 答案預設為超過上限的值
        full = total - 1  # n 個人同一組的 mask
        best = 0 if n%3 == 0 else 1  # 理論上的最佳解，如果 n 是 3 的倍數，可以平分成 3 組，最佳解為 0；否則最佳解為 1
        found = False  # 是否找到理論最佳解
        for s1 in range(1, total):
            # 如果 s1 不合法，找下一個
            if not valid[s1]: continue
            # 剪枝1，如果 s1 人數小於 n//3，找下一個
            if sz[s1] * 3 < n: continue
            # 用 XOR 找出剩下的人
            rest = full ^ s1
            # 窮舉 s2，逐步縮小 s2
            s2 = rest
            while s2 > 0:
                # 如果 s2 合法
                if valid[s2]:
                    # 用 XOR 找出第 3 組 s3
                    s3 = rest ^ s2
                    # 如果 s3 合法
                    if valid[s3]:
                        # 剪枝2，要求人數 s1 >= s2 >= s3
                        if sz[s1] >= sz[s2] >= sz[s3]:
                            ans = min(ans, sz[s1] - sz[s3])
                            # 剪枝3，找到理論最佳解，提早終止
                            if ans == best:
                                result.append(f"{best:d}\n")
                                found = True
                                break
                # 縮小 s2，不加這行會變成無窮迴圈
                s2 = (s2 - 1) & rest
            # 已經找到理論最佳解，中止迴圈
            if found: break
        # 如果沒有找到理論最佳解，ans == 1000，無解
        if not found:
            if ans == 1000: result.append("-1\n")
            else: result.append(f"{ans:d}\n")
    # 一次性輸出答案
    sys.stdout.write("".join(result))

if __name__ == "__main__":
    solve()

C++ 程式碼

使用時間約為 10 ms，記憶體約為 3.8 MB，通過測試。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m;  // n 個人，m 組關係
    while(cin >> n >> m) {
        /* 1. 用 bitmask 儲存朋友關係 */
        vector<int> adj (n, 0);
        for(int i = 0; i < m; i++) {
            int u, v;  // u, v 是朋友
            cin >> u >> v;
            u--; v--;  // 改成 0-index
            adj[u] |= (1 << v);  // 用 |= 修改 bitmask
            adj[v] |= (1 << u);
        }
       
        /* 2. 列出所有可能的組合，找合法的組合並計算人數 */
        int total = 1 << n;  // 組合的總數
        vector<bool> valid (total, true);  // 是否為合法的組合
        vector<int> sz (total, 0);  // 各組合的人數
        for(int mask = 1; mask < total; mask++) {  // 測試所有的組合
            sz[mask] = __builtin_popcount(mask);  // mask 有幾個 1，就是人數
            int u = __builtin_ctz(mask);  // mask 最後面有幾個 0，就是第 u 個人的索引值
            int prev = mask ^ (1 << u);  // mask 去掉 u 之後的組合
            // 如果 prev 是不是合法的組合或是 mask 之中有人是 u 的朋友，mask 不合法
            if (!valid[prev] || (mask & adj[u])) {  
                valid[mask] = false;
            }
        }
                
        /* 3. 找出分成 3 組的最多、最少人數差 */
        int ans = 1000, full = total - 1;  // 答案 ans 先設為超過上限的值，full 為包含所有人的 mask
        int best = (n%3 == 0) ? 0 : 1;  // 理論上的最佳解，如果 n 是 3 的倍數，可以平分為 3 組，人數差為 0；否則最少差 1
        bool found = false;  // 是否找到理論最佳解
        for(int s1 = 1; s1 < total; s1++) {  // 第 1 組 s1，人數最多
            // 如果 s1 不合法，找下一個
            if (!valid[s1]) continue;
            // 剪枝1，如果 s1 人數小於 n/3，不可能是解，找下一個
            if (sz[s1] * 3 < n) continue;
            // 用 XOR 取剩下的人數，窮舉 s2、s3
            int rest = full ^ s1;
            for(int s2 = rest; s2 > 0; s2 = (s2 - 1) & rest) { 
                // 如果 s2 不合法，找下一個
                if (!valid[s2]) continue;
                // 用 XOR 取第 3 組 s3
                int s3 = rest ^ s2;
                // s3 如果是空的或不合法，找下一個
                if (s3 == 0 || !valid[s3]) continue;
                // 剪枝2，要求各組人數 s1 >= s2 >= s3
                if (sz[s1] >= sz[s2] && sz[s2] >= sz[s3]) {
                    ans = min(ans, sz[s1] - sz[s3]);
                    // 剪枝3，如果找到理論上的最佳解，提前終止
                    if (ans == best) {
                        cout << best << "\n";
                        found = true;
                        break;
                    }
                }
            }
            if (found) break;
        }
        
        /* 4. 如果沒有找到理論最佳解輸出答案， ans == 1000 無解 */
        if (!found) {
            cout << (ans == 1000 ? -1 : ans) << "\n";
        }
    }
    return 0;
}