글 읽기 - 교실로 가는 길.. 어디서 틀린지 모르겠네요

previc1 2년 전 0

에드몬드 카프 이용해서 유량 구하고, k개의 경로 출력하도록 했는데 25%에서 계속 fail뜨네요. 반례가 있을까요..

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

vector <int> v[5004];
char cap[5004][5004];
char flow[5004][5004];
int par[5004];
int t, k, n;
int main(){
	while (1){
		scanf("%d%d", &k, &n);
		if (k == 0 && n == 0) break;
		for (int i = 0; i <= n; i++){
			v[i].clear();
			par[i] = -1;
			for (int j = 0; j <= n; j++){
				cap[i][j] = flow[i][j] = 0;
			}
		}

		for (int i = 1; i <= n; i++){
			while (1){
				char x;
				int b;
				scanf("%d%c", &b, &x);
				v[i].push_back(b);
				v[b].push_back(i);
				cap[i][b] = 1;
				cap[b][i] = 1;
				if (x == '\n')
					break;
			}
		}
		int Ans = 0;
		while (1){
			queue<int> q;
			q.push(1);
			for (int i = 1; i <= n; i++)
				par[i] = -1;
			while (q.size() && par[2] == -1){
				int now = q.front();
				q.pop();
				for (auto nxt : v[now]){
					if (cap[now][nxt] - flow[now][nxt] > 0 && par[nxt] == -1){
						q.push(nxt);
						par[nxt] = now;
					}
				}
			}
			if (par[2] == -1)
				break;
			for (int i = 2; i != 1; i = par[i]){
				flow[par[i]][i]++;
				flow[i][par[i]]--;
			}
			Ans++;
		}
		printf("Case %d:\n", ++t);
		if (Ans >= k){
			for (int i = 1; i <= k; i++){
				int now = 1;
				while (now != 2){
					printf("%d ", now);
					for (auto nxt : v[now]){
						if (flow[now][nxt] > 0){
							flow[now][nxt]--;
							now = nxt;
							break;
						}
					}
				}
				printf("2\n");
			}
		}
		else
			printf("Impossible\n");
		printf("\n");
	}
}

bupjae 2년 전 1

다음 입력 데이터에 대해서:

정답:

Impossible

오답:

1 3 5 6 2
1 4 5 7 2

bupjae 2년 전 1

윗 글에 입력 데이터가 안 들어가서 다시 씁니다.

previc1 2년 전 0

정점이 겹치면 안되는 조건을 놓쳤네요 감사합니다.

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

문제

문제

출처

ICPC

교실로 가는 길.. 어디서 틀린지 모르겠네요

previc1 2년 전 0

bupjae 2년 전 1

bupjae 2년 전 1

previc1 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회 / 고등학교 대회

출처

대학교 대회

도움말