BOJ)2660 회장뽑기

문제:icpc.me/2660

두 사람의 친구 관계가 주어질 때 어떤 사람이 가장 먼 친구 관계가 n다리 걸쳐서 친구관계가 된다면 그 사람의 점수는 n점이라 할 때 최소 점수를 갖는 사람들이 회장 후보가 된다. 회장 후보를 출력하는 문제이다.

두사람의 친구 관계를 cost가 1인 간선으로 표현한다면 플로이드 워셜을 통하여 n:n 최단거리를 구해주면 두 사람의 친구 관계가 몇다리 걸쳐있는지 알 수있다.

이를 이용하여 답을 구해주면 된다.

 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, x, y, a[51][51], r, b[51];
int main() {
    memset(a, 0x3f, sizeof(a));
    scanf("%d", &n);
    while (scanf("%d%d", &x, &y)!=EOF) {
        if (x == -1 && y == -1)break;
        a[x][y] = 1;
        a[y][x] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) 
                if (a[j][k] > a[j][i] + a[i][k])
                    a[j][k] = a[j][i] + a[i][k];
        }
    }
    r = 999999999;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)continue;
            b[i] = max(b[i], a[i][j]);
        }
        r = min(b[i], r);
    }
    int c = 0;
    for (int i = 1; i <= n; i++)
        if (r == b[i])c++;
    printf("%d %d\n", r, c);
    for (int i = 1; i <= n; i++)
        if (r == b[i])printf("%d ", i);
    return 0;
}