글 읽기 - 어디가 틀린건지 고수님들도와주세요

jerryprk 4년 전 0

일전의 소스는 각그룹에서 각노트에 합의 최대를 비교하여 출력하였는데

각 노드에서 연결할 수 있는 값의 최대가 최소값인 노드를 고를 수 있게 바꿨습니다

연결되어있지 않은곳은 그대로 자기자신이므로 들어갈 수 있게 해놨는데 어디가 문제일까요

#ifdef _DEBUG
#include "bits_stdc++.h"
#else
#include "bits/stdc++.h"
#endif
#pragma warning(disable:4996)
using namespace std;

int a, b, people, line;
#define MAX 105
#define INF MAX*MAX
vector <int> v[MAX];
vector <int> p;
int load[MAX][MAX];
void floyd() {
	for (int k = 1; k <= people; k++)
		for (int i = 1; i <= people; i++)
			for (int j = 1; j <= people; j++)
				if (i != j && load[i][j] > load[i][k] + load[k][j])
					load[i][j] = load[i][k] + load[k][j];
}
void find() {
	bool check[MAX];
	memset(check, 0, sizeof check);
	queue <int> q;
	for (int i = 1; i <= people; i++) {
		if (!check[i]) {
			pair<int, int> high = make_pair(0, INF);
			check[i] = true;
			q.push(i);
			while (!q.empty()) {
				int result = -1;
				int out = q.front(); q.pop();
				for (int k = 1; k <= people; k++) {
					if (load[out][k] != INF) {
						result = result > load[out][k] ? result : load[out][k];
					}
				}
				if (high.second > result) {
					high.first = out;
					high.second = result;
				}
				for (int i = 0; i < v[out].size(); i++) {
					int in = v[out][i];
					if (!check[in]) {
						check[in] = true;
						q.push(in);
					}
				}
			}
			p.push_back(high.first);
		}
	}
}
int main() {
#ifdef _CONSOLE
	freopen("input.txt", "r", stdin);
#endif
	scanf("%d %d", &people, &line);
	for (int i = 1; i <= people; i++)
		for (int j = 1; j <= people; j++)
				load[i][j] = INF;
	for (int i = 0; i < line; i++) {
		scanf("%d %d", &a, &b);
		v[a].push_back(b);
		load[a][b] = 1;
		load[b][a] = 1;
	}
	floyd();
	find();
	printf("%d\n", p.size());
	sort(p.begin(), p.end());
	for (int i = 0; i < p.size(); i++)
		printf("%d\n", p[i]);
}

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

문제

문제

출처

ICPC

어디가 틀린건지 고수님들도와주세요

jerryprk 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말