글 읽기 - 도저히 모르겠습니다..

medic_programmer 8년 전 0

어제 밤새 내내 고민하다가 오류를 찾지 못해서 도움을 구하고자 합니다. 어디서 코드 오타가 난건지, 아니면 알고리즘이 반례가 있는건지 ㅠㅠ

제가 구상한 알고리즘은 다음과 같습니다.

정점만 놔두고 일단 간선은 모두 지운 다음, 다음 규칙에 의해 필요한 간선을 하나씩 그어 나갑니다. 약간 플로이드+그리디 알고리즘인데요

1. 현재 입력받은 값 중 남아있는 값에서 최솟값을 택해 간선을 긋고, 플로이드를 돌린다.

2. 민호가 가진 값과 일치하게 되는 최솟값이 나왔다면 지운다. 남아있는 값들에 대해 1번을 반복한다.

- 만약 플로이드를 돌려 민호가 가진 값보다 작은 값이 나온다면 불가능 처리한다.

+) 영자님 문제 풀다가 어디서 틀린지 모르겠으면 틀린 test case를 확인할 수 있는 방법은 없나요?

#include<stdio.h>
#define T 999999999

int d[21][21],floyd[21][21];
int n;

void input()
{
	int i,j;
	for(i=1; i<=n; i++) for(j=1; j<=n; j++) scanf("%d",&d[i][j]); 
}

void floyd_warshall()
{
	int i,j,k;
	
	for(k=1; k<=n; k++){
		
		for(i=1; i<=n; i++){
			
			for(j=1; j<=n; j++){
				if(i==j || j==k || k==i) continue;	
				if(floyd[i][j] > floyd[i][k] + floyd[k][j]) floyd[i][j] = floyd[i][k] + floyd[k][j];
			}
		}
	}
}

void answering()
{
	int i,j,min,ii,jj,cnt=0;
	
	for(i=1; i<=n; i++) for(j=1; j<=n; j++) floyd[i][j] = T;
	for(i=1; i<=n; i++) floyd[i][i] = 0;
	
	while(1){
		
		min = T;
		
		for(i=1; i<=n; i++){
			
			for(j=i+1; j<=n; j++){
				
				if(min > d[i][j]){
					
					ii=i; jj=j;
					min = d[i][j];
					
				}
			}
		}
		
		if(min == T) break;
		
		cnt += min;
		
		floyd[ii][jj] = floyd[jj][ii] = min;
		
		floyd_warshall();
		
		for(i=1; i<=n; i++){
			
			for(j=i+1; j<=n; j++){
				
				if(floyd[i][j] == d[i][j]) d[i][j] = T;
				if(floyd[i][j] < d[i][j] && d[i][j] != T){
					printf("-1\n");
					return;
				}
			}
		}
	}
	
	printf("%d\n",cnt);
	return;
}

int main()
{
	
	scanf("%d",&n);
	
	input();
	answering();
	return 0;
}

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

문제

문제

출처

ICPC

도저히 모르겠습니다..

medic_programmer 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말