UVA 818 - Cutting Chains (暴力位掩碼 + 圖論判斷)

問題描述

給定若干環及其連接關係。打開一個環可將其切斷並用於連接其他環。求最少打開多少個環，使所有環連成一條鏈（非環）。n ≤ 15。

暴力枚舉子集

• 用整數 k 的二進制位表示哪些環被打開（1=打開）。枚舉 0..2ⁿ-1。
• 對每個子集，判斷剩餘未打開環構成的圖是否滿足：
  1. 所有頂點度數 ≤ 2（鏈或環的必要條件）。
  2. 無環存在（即圖為森林且每連通分量為路徑）。
• 若滿足，打開數 = popcount(k)。取最小值。
• 額外條件：打開的環數 ≥ 連通分量數 - 1（需要足夠環連接分量）。

判斷邏輯

bool hasCycle(int u, int fa, int* vis) {
    if(vis[u]) return true;
    vis[u]=1;
    for(v: neighbors) if(!(k&(1<

完整代碼
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 20;
int n, g[MAXN][MAXN], ans;
int k; // 當前枚舉的打開集合

int popcnt(int x) { return x? popcnt(x>>1)+(x&1):0; }

bool degreeOk() {
    for(int i=0;i2) return false;
    }
    return true;
}

bool noCycle() {
    int vis[MAXN]={0}, comp=0;
    for(int i=0;i= comp-1; // 打開環夠連接分量
}

int main() {
    int cas=1;
    while(cin>>n && n) {
        memset(g,0,sizeof(g));
        int a,b;
        while(cin>>a>>b, a!=-1) g[a-1][b-1]=g[b-1][a-1]=1;
        ans = n;
        for(k=0; k<(1<= ans) continue; // 剪枝
            if(degreeOk() && noCycle()) ans = popcnt(k);
        }
        cout << "Set " << cas++ << ": Minimum links to open is " << ans << endl;
    }
    return 0;
}

複雜度
2ⁿ × n²，n=15 時約 32768 × 225 ≈ 700 萬操作，極快。