취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 1658번 문제인 돼지 잡기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/1658 

K번째 오는 손님이 p번 돼지우리에 들어있는 돼지를 사는 경우, 이전에 p번 돼지우리를 열었던 (각각의) K'번 손님이 열었던 모든 돼지우리에 (처음에) 들어있던 돼지에 접근할 기회가 생긴다.

위의 관찰을 이용하면 source쪽에 손님들, sink쪽에 돼지우리들을 연결시켜두고 손님들 사이에 자신이 연 돼지우리중 하나라도 이전에 연 손님을 향한 가중치 INF의 간선을 추가해 만든 그래프에서 최대 유량을 구하는 것으로 문제를 해결할 수 있다.

아래는 제출한 소스코드이다.

#define NODE 1102
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <cstring>
using namespace std;

int source, sink;
int edge[NODE][NODE];
vector<int> G[NODE];
int level[NODE];

bool dinic_bfs() { // 현 단계의 level graph 생성; 리턴값: 성공여부
	memset(level, 0, sizeof(level));
	level[source] = 1;
	queue<int> que;
	que.push(source);
	while (!que.empty()) {
		int& cur = que.front();
		for (auto& node : G[cur]) {
			if (edge[cur][node] && level[node] == 0) {
				level[node] = level[cur] + 1;
				que.push(node);
			}
		}
		que.pop();
	}

	return level[sink];
}

int turn[NODE];

int dinic_dfs(int cur, int flow) { // flow값 오버플로우 주의
	if (cur == sink) return flow;
	int cursize = G[cur].size();
	for (int& i = turn[cur]; i < cursize; i++) {
		int& node = G[cur][i];
		if (edge[cur][node] && level[node] == level[cur] + 1) {
			int tmp = dinic_dfs(node, min(edge[cur][node], flow));
			if (tmp) {
				edge[cur][node] -= tmp;
				edge[node][cur] += tmp;
				return tmp;
			}
		}
	}

	return 0;
}

int dinic() { // 실제 maximum flow 계산
	int ret = 0;
	while (dinic_bfs()) {
		memset(turn, 0, sizeof(turn));
		int f;
		while (f = dinic_dfs(source, 1000000007)) ret += f;
	}

	return ret;
}

set<int> st[1001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	source = 0, sink = 1101;
	int M, N; cin >> M >> N;
	for (int m = 1; m <= M; m++) {
		int idx = m + 100;
		cin >> edge[idx][sink];
		G[idx].emplace_back(sink);
		G[sink].emplace_back(idx);
	}

	for (int i = 1; i <= N; i++) {
		set<int> tmp;
		int K; cin >> K;
		while (K--) {
			int x; cin >> x;
			st[x].insert(i);
			tmp.insert(x);
			edge[i][x + 100] = 1000000007;
			G[i].emplace_back(x + 100);
			G[x + 100].emplace_back(i);
		}
		
		set<int> tmptmp;

		for (auto& node : tmp) {
			for (auto& n : st[node]) {
				tmptmp.insert(n);
			}
		}

		for (auto& node : tmptmp) {
			if (node == i) continue;
			edge[i][node] = 1000000007;
			G[i].emplace_back(node);
			G[node].emplace_back(i);
		}

		int w; cin >> w;
		edge[source][i] = w;
		G[source].emplace_back(i);
		G[i].emplace_back(source);
	}

	cout << dinic();
}