C++[백준]1658번 돼지 잡기

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

1658번: 돼지 잡기

문제가 좀 조건대로 하면... 안풀리는 것인데 풀리니 이상하다 생각을 하고 푼 문제. (솔루션을 봤음..)

 

처음에 조건 3.을 제대로 보지 않아서  소스 - 돼지우리 - 사람 - 싱크 이렇게 노드를 연결하여 풀 수 있을 것이라 생각했다.

 

그런데 문을 열었을 때, 남은 돼지를 적절히 재분배 할 수 있다는 조건이 상당히 까다로워졌다.

 

도저히 문제를 해결못해서 솔루션을 봤다.

 

원래라면 디닉으로 풀리지 않는 시간 복잡도를 가졌다. O( (M*N)^2*(M*M)) 그래서 안될거라고 생각하고있었는데, 다른 사람들이 이렇게 풀면 풀린다고 한다...

아무래도 채점 데이터가 약한 것 같다.

 

솔루션

---

 

 

해법

1. 소스를 0으로 두고 첫째날 돼지우리를 1~M 까지 둔다.

2. X날 -> 다음 날 넘어가는 돼지 우리를  연결한다. (1~M) -> (M+1 ~ 2M, 일대일 대응)

3. 각 날짜에 오는 손님과 돼지 우리를 연결한다. (N*M+ 손님이 오는 날짜) 

    손님이 문을 여는 돼지 우리를 연결해 준다. (돼지우리를 1, 2를 열였으면, 1->2, 2->1 각각 간선을 연결한다.)

4. 각 손님과 싱크를 연결해 준다.

 

그림으로 표현하면 다음과 같다.

 

코드

---

#define INF 987654321
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct edge {
	int next, capacity, flow, inv;
};

int N, M;
vector<edge> V[100200];


int level[100200];
bool bfs(int s, int t) {
	fill(level, level + M * N + N + 2, -1);

	level[s] = 0;
	queue<int> Q;
	Q.push(s);

	while (!Q.empty()) {
		int cur = Q.front();
		Q.pop();

		for (auto& e : V[cur]) {
			if (level[e.next] == -1 && e.capacity > e.flow) {
				level[e.next] = level[cur] + 1;
				Q.push(e.next);
			}
		}
	}
	return level[t] != -1;
}

int start[100200];
int dfs(int cur, int t, int f) {
	if (cur == t) return f;

	for (int& i = start[cur]; i < V[cur].size();i++) {
		auto& e = V[cur][i];
		if (level[e.next] == level[cur] + 1 && e.capacity > e.flow) {
			int df = dfs(e.next, t, min(f, e.capacity - e.flow));
			if (df) {
				e.flow += df;
				V[e.next][e.inv].flow -= df;
				return df;
			}
		}
	}
	return 0;
}


int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> M >> N;

	for (int i = 1; i <= M; i++) {
		int value;
		cin >> value;
		V[0].push_back({ i,value,0,(int)V[i].size() });
		V[i].push_back({ 0,0,0,(int)V[0].size() - 1 });
	}

	for (int i = 2; i <= N; i++) {
		int cur = i * M;
		
		for (int  j= cur; j >(cur-M); j--) {
			V[j].push_back({ j - M,0,0,(int)V[j - M].size() });
			V[j - M].push_back({ j,INF,0,(int)V[j].size() - 1 });
		}
	}

	for (int i = 1; i <= N; i++) {
		vector<int> input;
		int cur = (i-1) * M;
		int tc;
		cin >> tc;
		while (tc--) {
			int value;
			cin >> value;
			input.push_back(value);
			//돼지 우리 - 사람과의 간선
			V[cur + value].push_back({ M * N + i,INF,0,(int)V[M * N + i].size() });
			V[M * N + i].push_back({ cur + value,0,0,(int)V[cur + value].size() - 1 });
		}

		int cap;
		cin >> cap;
		//사람 - 싱크
		V[M * N + i].push_back({ M * N + N + 1,cap,0,(int)V[M * N + N + 1].size() });
		V[M * N + N + 1].push_back({ M * N + i,0,0,(int)V[M * N + i].size() - 1 });

		if (i == N) break;
		for (int j = 0; j < input.size(); j++) { //돼지 우리 -> 다음 날 돼지 우리
			int node1 = cur + input[j];
			for (int k = 0; k < input.size(); k++) {
				if (j == k) continue;
				int node2 = i * M + input[k];

				V[node1].push_back({ node2,INF,0,(int)V[node2].size() });
				V[node2].push_back({ node1,0,0,(int)V[node1].size() - 1 });
			}			
		}
	}


	//총 M + 2N개의 노드.
	
	int maxflow = 0;
	while (bfs(0, M *N+N+1)) {
		fill(start, start + M * N + N + 2, 0);
		while (int df = dfs(0, M * N+N + 1, INF)) {
			maxflow += df;
		}
	}
	cout << maxflow << '\n';
}