글 읽기 - 유량 문제좀 도와주세요 ㅠㅠ

kkw564 6년 전 0

최대 유량을 잡고, 한번더 유량을 흘려보내며 S->T로 유량이 흐르는지 확인하는 과정으로 답을 구했습니다.

이때

//if (next == T)
// break;이 과정이 주석이어야만 AC이고 주석이 아니면 WA인데 왜 그런건가요..? 도저히 이해가 안되네요

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <memory.h>

#define INF 987654321

using namespace std;

typedef pair<int, int> pii;

vector<vector<int>> adj, c, f;

int main()
{
	int tc;
	scanf("%d", &tc);

	while (tc--)
	{
		int n, m;
		scanf("%d %d", &n, &m);

		f = c = vector<vector<int>>(n + 1, vector<int>(n + 1, 0));
		adj = vector<vector<int>>(n + 1);

		vector<pii> vc;

		for (int i = 0; i < m; i++)
		{
			int from, to, val;
			scanf("%d %d %d", &from, &to, &val);

			adj[from].push_back(to);
			adj[to].push_back(from); // 역방향 간선

			c[from][to] += val;

			vc.push_back({ from,to });
		}


		// 에드몬드 카프 알고리즘
		int totalFlow = 0, S = 1, T = n;

		while (1)
		{
			vector<int> prev(n + 1, -1);

			queue<int> q;
			q.push(S);

			while (!q.empty() && prev[T] == -1)
			{
				int cur = q.front();

				q.pop();

				for (int i = 0; i < adj[cur].size(); i++)
				{
					int next = adj[cur][i];

					if (prev[next] != -1)
						continue;

					if (c[cur][next] - f[cur][next] > 0)
					{
						q.push(next);

						prev[next] = cur;
					}

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

			if (prev[T] == -1)
				break;

			int flow = INF;

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

			for (int i = T; i != S; i = prev[i])
			{
				f[prev[i]][i] += flow;
				f[i][prev[i]] -= flow;
			}
			totalFlow += flow;
		}


		// 완전 중요한 간선인지 확인
		int ans = 0;
		for (int i = 0; i < vc.size(); i++)
		{
			int S = vc[i].first;
			int T = vc[i].second;

			vector<int> parent(n + 1, -1);

			queue<int> q;
			q.push(S);

			while (!q.empty() && parent[T] == -1)
			{
				int cur = q.front();
				q.pop();

				for (int i = 0; i < adj[cur].size(); i++)
				{
					int next = adj[cur][i];
					if (parent[next] != -1)
						continue;

					if (c[cur][next] - f[cur][next] > 0)
					{
						parent[next] = cur;
						q.push(next);
					}

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

			if (parent[T] == -1)
				ans++;
		}

		printf("%d\n", ans);
	}

	return 0;
}

kks227 6년 전 0

주석이 두 군데 있는데 둘 다 주석처리되어야 정답이고 둘 다 주석처리가 되어있지 않으면 오답이란 말씀이신가요?

kks227 6년 전 2

두 번째 주석 부분이 문제인 것 같네요. 어떤 간선을 잡고 그 시작점에서 유량을 흘려 반대편 끝점에 도달할 수 있으면 중요한 간선이 아니라는 것이 코드의 구조인데...두 번째 주석이 풀린다면 c[cur][next] - f[cur][next] > 0 이 구문이 거짓이어도 반복문을 나와버리네요.

1
4 4
1 2 1
2 4 1
2 3 1
3 4 1

이 케이스를 넣어보시면, 정답은 1이지만 주석이 해제되면 2가 나옵니다.

간선 (1, 2)만이 유일한 중요한 간선인데, 간선 (2, 4)를 체크하는 중에 아마도 비어있을 2->3->4 증가경로가 존재하겠지만 그냥 간선 (2, 4)가 이미 차있다는 이유로 나와버립니다.

1
4 4
1 2 1
2 3 1
3 4 1
2 4 1

실제로 이렇게 간선 순서만 바꿔서 (2, 4)를 맨 마지막 위치로 옮기면 답이 1이 나오는 걸 확인하실 수 있습니다. 이는 간선 순서상 2->3->4 경로를 먼저 체크하게 되고 증가 경로를 찾기 때문에 일어나는 일이죠.

kkw564 6년 전 0

감사합니다!! 와.. 명쾌하네요

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