POJ 1274 The Perfect Stall
解法
二部グラフの最大マッチングとみなせるので最大流問題をとけばいい
ford-fulkerson法が使える
#include <cstdio> #include <algorithm> #include <vector> using namespace std; const int MAX_N = 200, MAX_M = 200; int N, M; class edge{ public: int to, cap, flow, rev; edge(); edge(int t, int c, int r){ to = t; cap = c; flow = 0; rev = r; } }; vector<edge> a[1 + MAX_N + MAX_M + 1]; bool used[1 + MAX_N + MAX_M + 1]; bool dfs(int p, int s, int g){ if(p == g) return true; for(int i = 0; i < a[p].size(); i++){ if(used[a[p][i].to]) continue; if(a[p][i].cap > 0 && a[p][i].flow == 0){ //printf("%d -> %d\n", p, a[p][i].to); edge e = a[a[p][i].to][a[p][i].rev]; a[p][i].flow = 1; a[a[p][i].to][a[p][i].rev].cap = 1; a[a[p][i].to][a[p][i].rev].flow = 0; used[a[p][i].to] = true; if(dfs(a[p][i].to, s, g)) return true; else a[a[p][i].to][a[p][i].rev] = e; used[a[p][i].to] = false; } } return false; } int main(){ while(scanf("%d %d", &N, &M) != EOF){ for(int i = 0; i < 1 + MAX_N + MAX_M + 1; i++) a[i].clear(); for(int i = N + 1; i <= N + M; i++){ a[i].push_back(edge(1+N+M, 1, a[1+N+M].size() )); a[1+N+M].push_back(edge(i, 0, a[i].size() - 1 )); } for(int i = 1; i <= N; i++){ a[0].push_back(edge(i, 1, a[i].size() )); a[i].push_back(edge(0, 0, a[0].size()-1 )); } for(int i = 1; i <= N; i++){ int t; scanf("%d", &t); for(int j = 0; j < t; j++){ int to; scanf("%d", &to); to += N; a[i].push_back(edge(to, 1, a[to].size() ) ); a[to].push_back(edge(i, 0, a[i].size() - 1) ); } } int ans; for(ans = 0; ; ans++){ fill(used, used + 1 + N + M + 1, false); used[0] = true; if(!dfs(0, 0, 1 + N + M)) break; } printf("%d\n", ans); } return 0; }