내용

#include <bits/stdc++.h>
 
#define for1(s,n) for(int i = s; i < n; i++)
#define for1j(s, e) for(int j = s; j < e; j++)
 
#define foreach(k) for(auto i : k)
#define foreachj(k) for(auto j : k) 
#define pb(a) push_back(a)
#define sz(a) a.size()
#define all(vct) vct.begin(), vct.end()
#define uniq(vct) sort(all(vct));vct.erase(unique(all(vct)), vct.end())
#define fi first
#define se second
#define taxi_dis(a, b) abs(a.fi - b.fi) + abs(a.se - b.se)
 
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
 
typedef vector <int> iv1;
typedef vector <vector<int> > iv2;
 
typedef vector <ll> llv1;
typedef vector <vector <ll> > llv2;
 
typedef vector <ull> ullv1;
typedef vector <vector <ull> > ullv2;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
typedef pair<string, string> pss;
 
const ll INF = (ll)1e18;
 
struct Edge {
    ll v, capacity, rev;
    Edge(ll v, ll capacity, ll rev): v(v), capacity(capacity), rev(rev) {}
};
 
struct DINIC {
	int max_size, SRC, SINK;
	vector<vector<Edge>> vt;
	vector<ll> level;
	vector<ll> work;
	
	DINIC(int max_size) : max_size(max_size) {
		SRC = max_size - 2;
		SINK = max_size - 3;
		vt.resize(max_size);
		level.resize(max_size, 0);
		work.resize(max_size, 0);
	};
 
	void addEdge(ll start, ll end, ll capacity) {
		vt[start].emplace_back(end, capacity, (ll)vt[end].size());
		vt[end].emplace_back(start, 0, (ll)vt[start].size()-1);
	}
	
	void addEdgeFromSRC(ll end, ll capacity) {
		vt[SRC].emplace_back(end, capacity, (ll)vt[end].size());
		vt[end].emplace_back(SRC, 0, (ll)vt[SRC].size()-1);
	}
 
	void addEdgeToSINK(ll start, ll capacity) {
		vt[start].emplace_back(SINK, capacity, (ll)vt[SINK].size());
		vt[SINK].emplace_back(start, 0, (ll)vt[start].size()-1);
	}
	
	bool bfs() {
		fill(level.begin(), level.end(), -1);
		queue <ll> q;
		level[SRC] = 0;
		q.push(SRC);
 
		while(!q.empty()){
			int here = q.front(); q.pop();
			for (auto i : vt[here]) {
				ll there = i.v;
				if(level[there] == -1 && i.capacity > 0) {
					level[there] = level[here] + 1;
					q.push(there);
				}
			}
		}
 
		return level[SINK] != -1;
	}
	
	ll dfs(ll here, ll crt_capacity) {
		if(here == SINK) return crt_capacity;
 
		for(ll &i = work[here]; i < vt[here].size(); i++) {
			ll there = vt[here][i].v;
			ll capacity = vt[here][i].capacity;
 
			if(level[here] + 1 == level[there] && capacity > 0) {
				ll next_capacity = dfs(there, min(crt_capacity, capacity));
 
				if(next_capacity > 0) {
					vt[here][i].capacity -= next_capacity;
					vt[there][vt[here][i].rev].capacity += next_capacity;
					return next_capacity;
				}
			}
		}
		return 0;
	}
	
	ll flow() {
		ll ret = 0;
		while(bfs()) {
			fill(work.begin(), work.end(), 0);
 
			while(1) {
				ll flow = dfs(SRC, INF);
				if(!flow) break;
				ret += flow;
			}
		}
		return ret;
	}
};
 
void solve() {
    ll N, M;
    cin >> N >> M;
 
	DINIC mf = DINIC(N + M + 40);
 
    for1(0, N) {
        mf.addEdgeFromSRC(i, 1);
        ll S, a;
        cin >> S;
        while(S--) {
            cin >> a;
            mf.addEdge(i, a + N - 1, 1);
        }
    }
    for1(N, N+M) {
        mf.addEdgeToSINK(i,1);
    }
 
    cout << mf.flow();
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
  int tc = 1;
 
  while(tc--) {
    solve();
  }
}

연관 페이지

참고 문헌 / 사이트