글 읽기 - 20번의 틀렸습니다를 거치고 왔습니다..

kkw564 6년 전 0

도시를 왕복해야하는데 왜 저는 왕복을 못하는걸까요?

문제에서 source와 sink를 뺀 한번 방문한 노드는 다시 방문 할 수 없다고 하여, visit배열을 써서 구현했습니다.

하지만 저는 76퍼센트와 92퍼센트짜리 도시를 왕복못하고있습니다.

어떤 면에서 잘못됐는지 도와주시면 정말 감사히 도시 왕복을하겠습니다.

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

#define MAX 411
#define INF 987654321

using namespace std;

int c[MAX][MAX]; // capacity :: i->j로 가는 간선 용량
int f[MAX][MAX]; // flow :: i->j로 현재 흐르고 있는 유량
bool visit[MAX];

int main()
{
	int n, p;

	memset(c, 0, sizeof(c));
	memset(f, 0, sizeof(f));

	vector<int> adj[MAX];

	// 입력
	scanf("%d %d", &n, &p);
	for (int i = 0; i < p; i++)
	{
		int from, to;
		scanf("%d %d", &from, &to);

		c[from][to] = 1; // 용량을 추가해준다.
		c[to][from] = 1;

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

	int totalFlow = 0, S = 1, T = 2; // S :: source, T :: sink

	while (1)
	{
		int prev[MAX];
		memset(prev, -1, sizeof(prev));

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

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

			if (cur != S && cur != T)
				if (visit[cur])
					continue;

			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;

			if (i != S && i != T)
				visit[i] = true;
            
		}


		totalFlow += flow;
	}

	printf("%d\n", totalFlow);

	return 0;
}

lyzqm 6년 전 0

모델링이 잘못된거같습니다.

이 문제는 1,2번 정점을 제외한 나머지 정점은 단한번만 방문해야하는게 핵심인데

"정점분할"이라는 방식을 사용하면 해결할 수 있습니다.

예를 들어 3번정점을 3(in), 3(out)으로 두개의 정점으로 분할해서 이 사이의 용량을 1로 제한하면 유량이 한번흐르고 더이상 흐르지 못하므로

단 한번만 방문하는것을 구현할 수 있습니다.

ehddml3 6년 전 6

6 7

1 3
3 4
4 2
1 6
6 4
3 5
5 2

이런 식으로 강제적으로 첫 증가경로를 가로지르게 만들면 해당 그래프에서는 2가 나와야할 것 같은데 1이 나옵니다.

http://kks227.blog.me/22080488... 에 도시왕복 풀이에서 개념에 대한 그림이 있습니다. 노드 한 개를 내부 노드 두 개로 나누어서 그 두 노드 사이의 용량을 1로 두고 network flow를 돌리는 것인데 한번 읽어보시길..

kkw564 6년 전 0

@lyzqm

모델링 하는법을 한번 봤는데, 그런데 하나의 노드를 두개로 쪼개어 유량을 계산하는것과, 그냥 하나의 노드가 방문되었다면 true를 하는것과의 차이가 날수있나요?

smu201111192 6년 전 4

역변을 통해 유량을 되돌려야 될때 문제가 될 수 잇지않을까요 visit로 막아서 못 흘릴거 같아요

kkw564 6년 전 0

다들 감사합니다

플로우를 새로 공부해야겠다고 느꼈습니다.

제대로 알고있지 못했네요

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

문제

문제

출처

ICPC

20번의 틀렸습니다를 거치고 왔습니다..

kkw564 6년 전 0

lyzqm 6년 전 0

ehddml3 6년 전 6

kkw564 6년 전 0

smu201111192 6년 전 4

kkw564 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말