POJ 1637 Sightseeing tour：混合圖歐拉回路判定與最大流建模

題目大意

給定一個混合圖（含有向邊和無向邊），判斷是否存在歐拉回路（遍歷每條邊恰好一次並回到起點的迴路）。

核心理論：混合圖歐拉回路條件

1. 連通性：忽略方向後圖連通
2. 度數條件：對每個頂點 v，out_deg(v) - in_deg(v) 必須為偶數（設為 2·k_v）
3. 流可行性：將無向邊定向，使得每個頂點最終 out_deg = in_deg。構建流網絡判定是否可行。

最大流模型構建

1. 源點 S 向「出度需增加」的頂點連邊，容量 k_v
2. 「入度需增加」的頂點 向 匯點 T 連邊，容量 -k_v
3. 每條無向邊 在對應兩頂點間雙向連容量 1 的邊（代表選擇方向）
4. 有向邊直接計入初始度數，不進流網絡
5. 跑最大流，若最大流值 = 總需求和 Σ k_v，則可行

Dinic 算法完整實現

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 510
#define MAXE 5000000
#define INF 0x3f3f3f3f
#define S 0
#define T (MAX - 1)
using namespace std;

struct Edge { int x, y; bool directed; void Read() { int z; scanf("%d%d%d", &x, &y, &z); directed = z; } } edges[MAXE];

struct MaxFlow {
    int head[MAX], total;
    int nxt[MAXE], to[MAXE], cap[MAXE];
    int level[MAX];
    
    void init() { total = 1; memset(head, 0, sizeof head); }
    void add(int x, int y, int f) { nxt[++total] = head[x]; to[total] = y; cap[total] = f; head[x] = total; }
    void insert(int x, int y, int f) { add(x, y, f); add(y, x, 0); }
    
    bool bfs() {
        queue<int> q;
        memset(level, 0, sizeof level);
        level[S] = 1; q.push(S);
        while (!q.empty()) {
            int x = q.front(); q.pop();
            for (int i = head[x]; i; i = nxt[i])
                if (cap[i] && !level[to[i]]) {
                    level[to[i]] = level[x] + 1;
                    q.push(to[i]);
                    if (to[i] == T) return true;
                }
        }
        return false;
    }
    
    int dinic(int x, int f) {
        if (x == T) return f;
        int used = 0;
        for (int i = head[x]; i && used < f; i = nxt[i])
            if (level[to[i]] == level[x] + 1 && cap[i]) {
                int w = dinic(to[i], min(cap[i], f - used));
                cap[i] -= w; cap[i^1] += w; used += w;
            }
        return used;
    }
} solver;

int main() {
    int Tcase; cin >> Tcase;
    while (Tcase--) {
        solver.init();
        int n, m; scanf("%d%d", &n, &m);
        static int in[MAX], out[MAX];
        memset(in, 0, sizeof in); memset(out, 0, sizeof out);
        
        for (int i = 1; i <= m; ++i) {
            edges[i].Read();
            if (edges[i].x == edges[i].y) continue;  // 自環忽略
            if (!edges[i].directed) solver.insert(edges[i].x, edges[i].y, 1);
            ++out[edges[i].x]; ++in[edges[i].y];
        }
        
        // 構建流網絡
        int sum = 0;
        bool ok = true;
        for (int i = 1; i <= n; ++i) {
            int diff = out[i] - in[i];
            if (diff & 1) { ok = false; break; }  // 度差必須為偶數
            diff >>= 1;  // k_v
            if (diff > 0) { solver.insert(S, i, diff); sum += diff; }
            else if (diff < 0) solver.insert(i, T, -diff);
        }
        
        if (!ok) { puts("impossible"); continue; }
        
        int flow = 0;
        while (solver.bfs()) flow += solver.dinic(S, INF);
        
        puts(flow == sum ? "possible" : "impossible");
    }
    return 0;
}

關鍵點總結

• 自環不影響歐拉回路，直接忽略
• 度差奇數直接判不可能
• 無向邊建模為雙向容量 1 邊，流過方向即為最終定向
• Dinic 算法適用於此類稠密圖，複雜度 O(E√V) 實際極快