UVA 11045 My T-shirt suits me：二分圖最大流解法

UVA 11045 My T-shirt suits me：二分圖最大流

題目大意

有 N 件 T 恤（N 為 6 倍數），6 種尺碼各 N/6 件。M 位志工（N ≥ M），每人接受兩種尺碼。問能否讓所有人拿到合適尺碼。

建模為最大流

• 源點 S → 每位志工（容量 1）
• 志工 → 其接受的兩種尺碼（容量 1）
• 尺碼 → 匯點 T（容量 N/6）

跑最大流，若最大流 = M 則輸出 "YES"，否則 "NO"。

Dinic 實作要點

struct Dinic {
    struct Edge { int to, cap, rev; };
    vector> G;
    vector level, iter;
    Dinic(int n): G(n), level(n), iter(n) {}
    void add_edge(int fr, int to, int cap) {
        G[fr].push_back({to, cap, (int)G[to].size()});
        G[to].push_back({fr, 0, (int)G[fr].size()-1});
    }
    void bfs(int s) { /* 建立層次圖 */ }
    int dfs(int v, int t, int f) { /* 尋找增廣路 */ }
    int max_flow(int s, int t) { /* 主流程 */ }
};
// 尺碼映射：XS=1, S=2, M=3, L=4, XL=5, XXL=6
// 志工節點 1..M，尺碼節點 M+1..M+6，S=0, T=M+7

複雜度

N ≤ 36, M ≤ 30，Dinic 極快，O(E√V) 遠小於限制。