글 읽기 - 길이가 10n 이상인 negative cycle이 존재하는지 궁금합니다.

pichulia 4년 전 1

데이터 오류나 스페셜저지 오류는 아닌거같고..(아 설마 스페셜저지 오류인가?)

진짜 궁금해서 질문글 올려봅니다.

대충 아시다시피 벨만포드 알고리즘은 O(VE)=O(NM)에 동작합니다. 이는 최단경로가 되는 simple path의 길이가 길어봐야 n-1이기 때문입니다.

모든 간선을 돌면서 노드까지의 최단거리를 갱신하는 행위를 update라고 정의해보면, 한번 update 할 때마다 path의 길이가 1만큼 증가할 것입니다.

만약 1부터 n까지 가는 경로중에 negative cycle이 있다면(이 문제에서는 음수가 아니라 양수지만 뭐 아무튼) 그 cycle의 길이만큼 update를 수행하고나서 n까지 최단경로의 길이가 달라졌을 것입니다. 역으로 말하면 cycle의 길이만큼 update를 수행해도 n까지 최단경로의 길이가 달라지지 않았다면 negative cycle이 없음을 의미합니다.

이런 논리를 바탕으로 아래의 코드를 짰는데 무자비하게도 '틀렸습니다.'를 받았습니다.(동일한 알고리즘으로 타임머신 문제는 맞았습니다를 잘 받았습니다.)

문제가 되는 부분은 114번째 줄의 cnt 값의 상한입니다.

위에서 설명한 'cycle의 길이만큼 update를 수행'하는 부분입니다.

노드의 개수가 n개이기 때문에 negative cycle의 길이도 n 이하라고 저는 생각했습니다만.. 10n번을 돌아도 틀렸습니다를 받고있습니다. 하지만 해당 부분을 11n번 이상 돌리면 맞았습니다를 받고있습니다.

이것이 의미하는 바는, negative cycle의 길이가 10n 이상이라는건데.. 아무리 생각해도 이렇게나 긴 cycle이 존재할리가 없을것 같습니다.

만약 제 논리에 문제가 있는 것이라면 11n이라는 횟수도 데이터에 의해서 우연히 맞은 것이고, cycle의 길이의 하한선을 나타내는 무언가가 있어서 그 친구를 알아내지 못한다면 저는 이 문제는 못푼것과 다름이 없게 됩니다...

저의 풀이나 논리에서 어느 부분이 잘못되었으며, 반례로 어떤게 있을지 같이 찾아봐주시길 부탁드립니다.

감사합니다ㅠ

#include<stdio.h>
#include<algorithm>
#include<vector>
#include<assert.h>
using namespace std;
using pii = pair<int, int>;
using pll = pair<long long int, long long int>;
using pli = pair<long long int, int>;
using pil = pair<int, long long int>;
using lld = long long int;
#define INF 1000000000009LL
int n, m;
vector<pil> v[2009];
int p[2009];
lld d[2009];
int res[2009];
int rl;
bool check() {
	int i, j, k;
	for (i = rl - 2; i >= 0; i--) {
		int pi = res[i + 1];
		int qi = res[i];
		bool valid = false;
		for (j = 0; j < v[pi].size(); j++) {
			if (v[pi][j].first == qi) {
				if (d[qi] < d[pi] + v[pi][j].second)
					return false;
				if (d[qi] == d[pi] + v[pi][j].second)
					valid = true;
			}
		}
		if (!valid)return false;
	}
	return true;
}
bool check_2() {
	int i, j, k;
	for (i = 1; i < rl; i++) {
		int pi = res[i - 1];
		int qi = res[i];
		bool valid = false;
		for (j = 0; j < v[pi].size(); j++) {
			if (v[pi][j].first == qi) {
				if (d[qi] < d[pi] + v[pi][j].second)
					return false;
				if (d[qi] == d[pi] + v[pi][j].second)
					valid = true;
			}
		}
		if (!valid)return false;
	}
	return true;
}
int visited[2009];
bool dfs(int si)
{
	int i, j, k;
	res[rl++] = si;
	visited[si] = 1;
	if (si == n - 1) {
		assert(check_2());
		for (i = 0; i < rl; i++) {
			printf("%d ", res[i] + 1);
		}
		return true;
	}
	for (i = 0; i < v[si].size(); i++) {
		j = v[si][i].first;
		if (visited[j] == 0 && d[j] == d[si] + v[si][i].second) {
			if (dfs(j))
				return true;
		}
	}
	rl--;
	visited[si] = 0;
	return false;
}
int main() {
	int i, j, k, l;
	scanf("%d %d", &n, &m);
	assert(2 <= n && n <= 100);
	assert(1 <= m && m <= 20000);
	while (m--) {
		scanf("%d %d %d", &i, &j, &k);
		assert(1 <= i && i <= n);
		assert(1 <= j && j <= n);
		assert(-1000 <= k && k <= 1000);
		i--; j--;
		v[i].push_back(pil(j, k));
	}
	for (i = 0; i < n; i++) {
		d[i] = -INF;
        p[i] = n+1;
	}
	d[0] = 0;
	p[0] = -1;
	for (int cnt = 0; cnt < 2 * n; cnt++) {
		for (i = 0; i < n; i++) {
			if (d[i] == -INF)continue;
			for (j = 0; j < v[i].size(); j++) {
				k = v[i][j].first;
				if (d[k] < d[i] + v[i][j].second) {
					d[k] = d[i] + v[i][j].second;
					p[k] = i;
				}
			}
		}
	}
	bool valid = true;
	if (d[n - 1] == -INF) valid = false;
	else {
		lld prev = d[n - 1];
        // HERE IS PROBLEM!!
		for (int cnt = 0; cnt < 10 * n; cnt++) {
			for (i = 0; i < n; i++) {
				for (j = 0; j < v[i].size(); j++) {
					k = v[i][j].first;
					if (d[k] < d[i] + v[i][j].second) {
						d[k] = d[i] + v[i][j].second;
					}
				}
			}
		}
		if (prev != d[n - 1])
			valid = false;
	}
	if (valid) {
		/*
		i = n - 1;
		while (i >= 0) {
			res[rl++] = i;
			i = p[i];
            assert(i<n);
			assert(rl < 2 * n);
		}
		assert(check());
		while(rl--){
			printf("%d ",res[rl]+1);
		}
		*/
		dfs(0);
	}
	else {
		printf("-1\n");
	}

}

pichulia 4년 전 0

트위터를 통해 해결했습니다. 확인결과 최악의 경우 wn번의 update가 필요할 수도 있다는 것을 알아냈습니다...

게시글에 있던 논리에서 빠진 것은..최단경로가 여러개 있을 수 있다는 것이였습니다 -_-;;

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

문제

문제

출처

ICPC

길이가 10n 이상인 negative cycle이 존재하는지 궁금합니다.

pichulia 4년 전 1

pichulia 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말