ZeroJudge 解題筆記：l925. P.8 值班警衛 (Guard)

作者：王一哲
日期：2025年5月26日



ZeroJudge 題目連結：l925. P.8 值班警衛 (Guard)

解題想法

産生警衛的組合之後立刻檢查這個組合是否能覆蓋所有的邊，不需要把所有組合都儲存起來，可以少用一點記憶體。

Python 程式碼

寫法1，産生所有可能的警衛組合，先存入串列中，最後才檢查每個組合是否能覆蓋所有的邊。最後一筆測資超出記憶體上限。

import sys

def sove(N, M, edges):  # 輸入節點數量N、邊的數量M、邊 edges
    # 産生所有可能的組合
    all_combs = []
    for i in range(1 << N):  # i = 0 ~ 2**N - 1
        comb = []  # 組合
        for j in range(N):  # j = 0 ~ N-1
            if (i >> j) & 1:  # 如果 i 向右移 j 位等於 1，comb 加入 j
                comb.append(j + 1)  # 因為編號從 1 開始
        all_combs.append(comb)  # comb 加入 all_combs
    # 找到可以複蓋所有邊而且數量最少的組合
    imin = N  # 最少的數量，預設為所有的節點數量N
    for comb in all_combs:  # 依序從 all_combs 取出 comb
        covered = True  # 是否覆蓋所有的邊，預設為 True
        for u, v in edges:  # 從 edges 依序讀取每個邊的端點 u, v
            if u not in comb and v not in comb:  # 如果 u, v 都不在 comb 之中
                covered = False; break  # comb 不能覆蓋所有的邊，中止迴圈
        if covered: imin = min(imin, len(comb))  # 如果 comb 可以覆蓋所有的邊，更新 imin
    return imin  # 回傳 imin

for line in sys.stdin:
    N, M = map(int, line.split())
    edges = [list(map(int, input().split())) for _ in range(M)]
    print(min_guards(N, M, edges))

寫法2，由寫法1修改而成，産生警衛的組合之後立刻檢查這個組合是否能覆蓋所有的邊，可以少用一點記憶體。使用時間約為 2 s，記憶體約為 3.3 MB，通過測試。

import sys

def solve(N, M, edges):  # 輸入節點數量N、邊的數量M、邊 edges
    imin = N  # 最少的數量，預設為所有的節點數量N
    for i in range(1 << N):  # i = 0 ~ 2**N - 1
        comb = []  # 組合
        for j in range(N):  # j = 0 ~ N-1
            if (i >> j) & 1:  # 如果 i 向右移 j 位等於 1，comb 加入 j
                comb.append(j + 1)  # 因為編號從 1 開始
        covered = True  # 是否覆蓋所有的邊，預設為 True
        for u, v in edges:  # 從 edges 依序讀取每個邊的端點 u, v
            if u not in comb and v not in comb:  # 如果 u, v 都不在 comb 之中
                covered = False; break  # comb 不能覆蓋所有的邊，中止迴圈
        if covered: imin = min(imin, len(comb))  # 如果 comb 可以覆蓋所有的邊，更新 imin
    return imin  # 回傳 imin

for line in sys.stdin:
    N, M = map(int, line.split())
    edges = [list(map(int, input().split())) for _ in range(M)]
    print(solve(N, M, edges))

C++ 程式碼

使用時間約為 0.2 s，記憶體約為 284 kB，通過測試。

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;

int solve(int N, int M, int edges[][2]) {  // 輸入節點數量N、邊的數量M、邊 edges
    int imin = N;  // 最少的數量，預設為所有的節點數量N
    for(int i=0; i < (1<<N); i++) {  // i = 0 ~ 2**N - 1
        set<int> comb;  // 組合
        for(int j=0; j<N; j++) {  // j = 0 ~ N-1
            if ((i >> j) & 1) comb.insert(j+1);  // 如果 i 向右移 j 位等於 1，comb 加入 j
        }
        bool covered = true;  // 是否覆蓋所有的邊，預設為 True
        for(int j=0; j<M; j++) {  // 從 edges 依序讀取每個邊的端點 u, v
            int u = edges[j][0], v = edges[j][1];
            if (comb.count(u) != 1 && comb.count(v) != 1) {  // 如果 u, v 都不在 comb 之中
                covered = false; break;  // comb 不能覆蓋所有的邊，中止迴圈
            }
        }
        if (covered) imin = min(imin, (int)comb.size());  // 如果 comb 可以覆蓋所有的邊，更新 imin
    }
    return imin;  // 回傳 imin
}

int main() {
    int N, M;
    while(scanf("%d %d", &N, &M) != EOF) {
        int edges[M][2];
        for(int i=0; i<M; i++) scanf("%d %d", &edges[i][0], &edges[i][1]);
        printf("%d\n", solve(N, M, edges));
    }
    return 0;
}