POJ 1637 混合圖歐拉回路：網絡流建模與 Dinic 算法實現

問題定義

混合圖包含有向邊與無向邊。判斷是否存在歐拉回路（恰好走過每條邊一次並回到起點）。

必要條件轉化

1. 無向邊可視為雙向有向邊，但只能選擇一個方向使用；
2. 歐拉回路存在 ⇔ 每個頂點入度 = 出度；
3. 對於無向邊 (u,v)，需決定方向：u→v 或 v→u，相當於在 u 的出度 +1、v 的入度 +1，或相反。

網絡流建模

步驟 1：處理有向邊

直接計算每個頂點的淨流量：in[v] - out[v]。有向邊固定貢獻。

步驟 2：無向邊建模為流量分配

• 源點 S、匯點 T；
• 淨流量 > 0 的頂點（需流入）連向 T，容量 = 淨流量/2；
• 淨流量 < 0 的頂點（需流出）從 S 連出，容量 = |淨流量|/2；
• 每條無向邊 (u,v) 在 u 和 v 之間雙向加容量 1 的邊（代表方向選擇）。

步驟 3：判斷可行性

• 所有頂點淨流量必須為偶數（否則無法平衡）；
• 跑最大流，若流量 = Σ(正淨流量/2)，則存在歐拉回路。

Dinic 算法關鍵點

struct Edge { int v, w, next; } e[MM];
int head[MN], vis[MN], cnt;

bool bfs(int s, int t) { ... }  // 分層圖
int dfs(int u, int flow, int t) { ... }  // 阻塞流
int dinic(int s, int t) { ... }  // 主循環

注意：邊數上限 MM = 100005，點數 MN = 500，需開足夠大數組。

完整求解流程

bool solve(int n, int m) {
    // 1. 初始化
    memset(head, -1, sizeof(head));
    memset(in, 0, sizeof(in));
    cnt = 0;
    
    // 2. 處理有向邊，計算 in[]
    for (i = 0; i < m; i++) {
        --in[u], ++in[v];
        if (!directed) add(u, v, 1);  // 無向邊加入流網絡
    }
    
    // 3. 檢查奇數度
    for (i = 1; i <= n; i++) if (in[i] & 1) return false;
    
    // 4. 建立超級源匯
    int sum = 0;
    for (i = 1; i <= n; i++) {
        if (in[i] < 0) add(0, i, -in[i]/2);
        if (in[i] > 0) add(i, n+1, in[i]/2), sum += in[i]/2;
    }
    
    // 5. 最大流判斷
    return sum == dinic(0, n+1);
}

複雜度分析

• Dinic 在二分圖類網絡上極快，實際接近 O(E√V)；
• 總體 O(T × maxflow)，輕鬆通過時限。

核心心得

混合圖歐拉回路 = 度數平衡 + 方向分配可行性。將「無向邊選方向」轉化為「流量分配」，是將組合決策問題降維為網絡流的經典範例。