글 읽기 - 열혈강호 문제 방문 처리(?) 여부 질문 있습니다!

park780172 4년 전 0

우선 상당히 길고, 약간 복잡한 질문이라서 읽어주신 것만으로도 감사합니다.

구글링(?)을 해봐도 마땅히 제가 원하는 답을 얻지 못 하여 부득이하게 이 곳에 질문해봅니다.

MCMF 공부 중에 연습 문제로 이 문제를 풀어보았습니다.

제가 첨부한 코드는 일단 틀린 코드이고,
105번 째 줄을 101번 째 줄(주석)로 고치면 통과됩니다.

하지만, 제가 6086번 최대 유량을 풀 때는
http://boj.kr/1dafeccac76449c9a1e86861e80bd8b6에 있는 35번 째 줄처럼
'd[next] == -1'(아직 방문을 안 했다면)을 구현하였음에도 통과하였고,

11657번 타임머신을 SPFA로 풀 때는
http://boj.kr/f0280b69e90746dc916f760829a93632에 있는 47번 째 줄처럼
'dist[here] != INF'(출발점에서는 가지 못 하는 정점일 때는 무시)을 구현하였고 통과하였습니다.

그런데

이 문제(MCMF)에서는 위의 2가지 조건을 구현하면 틀리고,
왜 빼야 통과되는지 궁금합니다..

MCMF의 개념이 구글링해도 잘 나오지는 않더라구요 ㅠㅠ 뭔가 문제 위주로만 있어서..

#include <bits/stdc++.h>

using namespace std;

#define MAX 803
#define INF 2e9
#define work 400
#define S 800 + 1
#define T 800 + 2

int N, M;

int c[MAX][MAX], f[MAX][MAX], w[MAX][MAX];

vector<int> v[MAX];

bool inQ[MAX];

int main(void)
{
	/*
	S : 801
	직원 : 1 ~ 400
	일 : 401 ~ 800
	T : 802
	*/

	int work_count, work_number, money;

	scanf("%d %d", &N, &M);

	// S와 직원 연결
	for (int i = 1; i <= N; i++)
	{
		c[S][i] = 1;
		v[S].push_back(i);
		v[i].push_back(S);
	}

	// 일과 T을 연결
	for (int i = 1; i <= M; i++)
	{
		c[i + work][T] = 1;
		v[i + work].push_back(T);
		v[T].push_back(i + work);
	}

	// 입력
	for (int i = 1; i <= N; i++) // 직원
	{
		scanf("%d", &work_count);

		for (int j = 0; j < work_count; j++) // 일
		{
			scanf("%d %d", &work_number, &money);

			v[i].push_back(work_number + work);
			v[work_number + work].push_back(i);

			w[i][work_number + work] = money;
			w[work_number + work][i] = -money;

			c[i][work_number + work] = 1; // 양방향 아님
		}
	}

	int canWork_count = 0, min_cost = 0;

	// SPFA + Network Flow
	while (true)
	{
		int d[MAX], dist[MAX];

		fill(d, d + MAX, -1); // 방문 처리(-1로 초기화)
		fill(dist, dist + MAX, INF); // 최소 비용(무한대로 초기화)

		queue<int> q;

		memset(inQ, false, sizeof(inQ));

		q.push(S);
		inQ[S] = true;
		dist[S] = 0;

		// BFS
		while (!q.empty())
		{
			int qSize = q.size();

			while (qSize--)
			{
				int here = q.front();

				q.pop();

				inQ[here] = false;

				/*
				아래 105번 째 줄을 바로 아래에 있는 코드로 바꿔야 통과합니다.

				if (c[here][next] - f[here][next] > 0 && dist[next] > dist[here] + w[here][next])
				*/

				for (auto next : v[here])
					if (d[next] == -1 && dist[here] != INF && c[here][next] - f[here][next] > 0 && dist[next] > dist[here] + w[here][next])
					{
						// 최소 비용(dist) 갱신 
						dist[next] = dist[here] + w[here][next];

						d[next] = here; // 경로 기억

						if (!inQ[next]) // queue 안에 없다면
						{
							inQ[next] = true;
							q.push(next);

							if (next == T) break; 
						}
					}			
			}
		}

		// 경로를 다 찾았으면 탈출
		if (d[T] == -1) break;

		int Flow = INF;

		// 끝 점부터 탐색
		for (int i = T; i != S; i = d[i])
			Flow = min(Flow, c[d[i]][i] - f[d[i]][i]);

		// 끝 점부터 다시 흐를 수 있는 용량(f) 갱신
		for (int i = T; i != S; i = d[i])
		{
			min_cost += Flow * w[d[i]][i]; // 사실 이걸 잘 모르겠음.
			f[d[i]][i] += Flow;
			f[i][d[i]] -= Flow;
		}

		++canWork_count;
	}

	printf("%d\n%d\n", canWork_count, min_cost);

	return 0;
}

sillsill777 4년 전 3

d[next]==-1 부분 때문에 오답이 됩니다.

SPFA의 기본 논리는 벨만 포드입니다. 벨만 포드 알고리즘에서는 어떤 노드에 방문했는지 여부를 따지지 않습니다.

아마 노드의 방문 여부를 체크하려고 하시는게 다익스트라 때문인 것으로 보이는데,

다익스트라의 경우 선택된 노드는 그 노드까지의 최소 비용이 보장 되기 때문에 노드 방문 여부를 통해 이전에 이 노드를 방문했었는지

체크하는 것입니다.-> 이전에 방문했던 적이 있므면 다시 방문한 이 동일한 노드 까지의 비용은 최소한 같거나 크기 때문.

그러나 벨만포드는 이미 방문했었던 노드라도 후에 더 작은 값이 들어 올 수 있기 때문에 위와 같이 이미 방문했는지 여부를 파악하여 그 노드 값의 갱신을 아예 제외 시켜버리니 오답이 됩니다. d[next]==-1부분만 지우고 제출하면 통과됩니다.

여담으로

for (int i = T; i != S; i = d[i]) Flow = min(Flow, c[d[i]][i] - f[d[i]][i]);

부분은 필요가 없습니다. 이 문제의 경우 만약 flow를 더 흘려보낼 수 있는 상황이라면 이는 무조건 flow가 1이기 때문입니다.

따라서

for (int i = T; i != S; i = d[i]) { min_cost += 1 * w[d[i]][i]; f[d[i]][i] += 1; f[i][d[i]] -= 1; } -> 이렇게 해줘도 맞는 답이 됩니다.

sillsill777 4년 전 1

추가로, dist[here] != INF부분 또한 필요가 없습니다. 있어도 상관은 없으나 없어도 됩니다

위의 조건이 필요한 것은 기존 벨만 포드로, 시작점에서 here까지 길이 없어서 INF 값이 있는 상태에서 here->next가 음의 간선일 경우

시작점에서 next까지 here을 거친 경로는 없으나(시작점에서 here의 길이 없으므로) INF+음의 가중치의 값이 새로 저장 되는 문제 때문에 위의 조건이 필요합니다.

그러나 SPFA의 경우는 queue를 사용하고, queue에는 시작점에서 here까지 길이 존재해야 queue에 here이 push되기 때문에 위의 조건은 검사할 필요가 없습니다.

잘 이해가 안가시면 답글 달아주시기 바랍니다.

park780172 4년 전 1

@sillsill777

댓글 정말 감사합니다.

제가 벨만 포드와 다익스트라의 기본 원리를 잘 알지 못 했네요.

상세한 설명 감사합니다.

정리하자면,

[벨만 포드]
1. 어떤 노드를 방문했는지 따지지 않음.
2. 모든 정점을 방문해서 거리를 갱신해야되기 때문임.
3. dist[here] != INF 조건은 필요함.(시작점에서 here까지의 길이 없고, 시작점→here→next까지의 거리가 갱신되버리기 때문임)

[SPFA]
1. queue와 inQ 배열에는 시작점에서 here까지 길이 존재해야 queue에 here이 push 될 수 있기 때문에
dist[here] != INF 조건이 필요하지 않음.
2. 기본 원리는 벨만 포드이기 때문에 방문 했는지 안 했는지는 중요 하지 않음.
3. 벨만 포드와 마찬가지로 작은 값이 들어올 수 있기 때문에 계속 갱신해야 됨.

[다익스트라]
1. 이미 갱신된 정점에 대해서는 출발점에서 그 노드까지의 최소 비용이 보장된 상태이기
때문에 방문 처리를 해야함.

이네요.

여담까지 무척 감사합니다.

MCMF에 익숙하지가 않아서 좀 더 연습이 필요한 알고리즘이네요. 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

열혈강호 문제 방문 처리(?) 여부 질문 있습니다!

park780172 4년 전 0

sillsill777 4년 전 3

sillsill777 4년 전 1

park780172 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말