HDU 5305 Friends：DFS 枚舉邊的線上/線下分配

問題描述

有 n ≤ 8 個人，m 對好友關係。每對好友可選「線上」或「線下」模式。要求每個人的線上好友數等於線下好友數。求滿足條件的分配方案數。

解題思路：DFS + 剪枝

因 n ≤ 8，m ≤ 28，總方案數 2^m ≤ 2^28 ≈ 2.6億，直接暴力略大，但可利用對稱性與剪枝大幅優化：

• 若 m 為奇數，直接返回 0（因每人線上=線下 ⇒ 總邊數為偶）。
• 若某人總度數為奇數，也無解。
• DFS 遞歸處理每條邊，嘗試分配為線上/線下，維護每人目前的線上/線下計數，若超過總度數一半則剪枝。
• 所有邊處理完檢查是否所有滿足條件，計數器加一。

代碼框架

int n, m;
int U[30], V[30]; // 邊列表
int online[10], offline[10], degree[10];
long long ans;

void dfs(int idx) {
    if (idx == m) {
        ans++; return;
    }
    int u = U[idx], v = V[idx];
    // 嘗試線上
    if (online[u] < degree[u]/2 && online[v] < degree[v]/2) {
        online[u]++; online[v]++;
        dfs(idx+1);
        online[u]--; online[v]--;
    }
    // 嘗試線下
    if (offline[u] < degree[u]/2 && offline[v] < degree[v]/2) {
        offline[u]++; offline[v]++;
        dfs(idx+1);
        offline[u]--; offline[v]--;
    }
}

int main() {
    int T; scanf("%d",&T);
    while (T--) {
        scanf("%d%d",&n,&m);
        memset(degree,0,sizeof(degree));
        for (int i=0;i