2660번: 회장뽑기

https://www.acmicpc.net/problem/2660


$O(n^3)$

친구 사이이면 가중치를 1, 그렇지 않으면 무한대로 설정하고 플로이드 알고리즘을 돌린다.
회원 x의 점수는 x와 나머지 회원간 최대 가중치이다.

#include<cstdio>
int d[51][51], n, x, y, maxi[51], can = 1e9, cnt;
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) if (i^j) d[i][j] = 1e9;
    while (scanf("%d%d", &x, &y), ~x) d[x][y] = d[y][x] = 1;
    for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++)
        if (d[i][j] > d[i][k] + d[k][j]) d[i][j] = d[i][k] + d[k][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) if (maxi[i] < d[i][j]) maxi[i] = d[i][j];
        if (can > maxi[i]) can = maxi[i], cnt = 0;
        cnt += can == maxi[i];
    }
    printf("%d %d\n", can, cnt);
    for (int i = 1; i <= n; i++) if (maxi[i] == can) printf("%d ", i);
    return 0;
}