BOJ 11376: 열혈강호 2 작성일 2020-02-16 https://www.acmicpc.net/problem/11376 2월동안 187문제 풀기(지난달 누적 87개) (32/187) 열혈강호 1에서 유량만 바꾸면 맞는 문제. 훨신 빠른 풀이도 있는듯 하다. Bimat 전용 풀이가 있는지 확인할 것. Harpcroft-Karp 알고리즘 공부 필요 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include <bits/stdc++.h> using namespace std; const int SZ = 1000; int N, M, k, w, cap[2*SZ+2][2*SZ+2]; vector<int> adj[2*SZ+2]; const int S = 0, T = 2*SZ+1, INF = 0x7ffff; void fillInput() { cin >> N >> M; for(int i = 1; i <= N; i++) { cin >> k; cap[S][i] = 1; adj[S].push_back(i); adj[i].push_back(S); for(int j = 0; j < k; j++) { cin >> w; w += SZ; adj[i].push_back(w); adj[w].push_back(i); cap[i][w] = 1; } } for(int i = SZ+1; i <= SZ + M; i++) { cap[i][T] = 1; adj[i].push_back(T); adj[T].push_back(i); } } int bfs(vector<int>& parent) { fill(parent.begin(), parent.end(), 0); queue<pair<int,int>> q; parent[S] = -1; q.push({S, INF}); while(q.size()) { int cur = q.front().first; int flow = q.front().second; q.pop(); for(int next : adj[cur]) { if(!parent[next] && cap[cur][next]) { parent[next] = cur; int newFlow = min(flow, cap[cur][next]); if (next == T) return newFlow; q.push({next, newFlow}); } } } return 0; } void print() { for(auto row: cap) { for(int i = 0; i < 2*SZ+2; i++) cout << row[i] << " "; cout << "\n"; } cout << "\n"; } int maxflow() { int flow = 0; vector<int> parent(2*SZ+2); int newFlow = 0; //print(); while (newFlow = bfs(parent)) { flow += newFlow; int cur = T; while (cur != S) { int prev = parent[cur]; cap[prev][cur] -= newFlow; cap[cur][prev] += newFlow; cur = prev; } //print(); } return flow; } int main() { fillInput(); cout << maxflow(); }