Codeforces Round #318 題解：三元組最小度數和 (暴力枚舉優化)

問題描述 (CF 318B / 574B? 實為 CF 574B Bear and Three Musketeers)

給定 n 個節點，m 條邊 (無向圖)。找三個兩兩相連的節點 (三角形)，使其度數之和最小。輸出最小度數和 - 6 (扣除三角形內部 3 條邊各算兩次)。無三角形輸出 -1。n≤4000, m≤4000。

解法一：三重暴力枚舉 (利用邊稀疏)

m≤4000，圖很稀疏。枚舉所有邊 (u,v)，再枚舉 u 的鄰居 w，檢查 v-w 是否有邊。用鄰接矩陣 O(1) 查邊。複雜度 O(m * 平均度) ≈ O(m * 2m/n) ≤ O(4000*2) = 8000，極快。

關鍵代碼 (C++)

bool adj[MAXN][MAXN];
vector G[MAXN];
int deg[MAXN];

int main() {
    int n,m; scanf("%d%d",&n,&m);
    for (int i=0;i u) { // 枚舉邊 u-v, 避免重複
            for (int w : G[v]) if (w > v) { // 枚舉 v 的鄰居 w
                if (adj[u][w]) { // u-v-w 成三角形
                    ans = min(ans, deg[u]+deg[v]+deg[w]-6);
                }
            }
        }
    }
    printf("%d\n", ans==INF?-1:ans);
    return 0;
}

解法二：優化枚舉順序 (按度數排序)

為進一步優化，可將節點按度數排序，僅枚舉「低度節點」作為三角形的一角，或用節點排序後的邊方向 (低度指向高度) 構建有向圖，保證出度 ≤ √(2m)。但本題數據範圍下解法一已足夠。

關鍵點

• 鄰接矩陣查邊 O(1)：n=4000 矩陣 16e6 bool ≈ 16MB，可接受。
• 枚舉邊 + 共同鄰居：標準三角形計數模板。
• 度數和 - 6：三角形內 3 條邊每條在三個度數中各算一次，共 6 次，需扣除。

總結

CF 574B (原文標題可能為 Round #318 某題) 展示了稀疏圖三角形枚舉的經典技巧：鄰接矩陣 + 枚舉邊 + 遍歷較小度端的鄰居。對於 m≤4000，暴力三重循環配合 O(1) 判邊即可輕鬆 AC，無需複雜優化。