티스토리 뷰

알고리즘 관련/BOJ

BOJ)2660 회장뽑기

JASON 자손9319 2017. 3. 23. 19:39

문제:icpc.me/2660


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


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


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


 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int n, x, y, a[51][51], r, b[51];
int main() {
    memset(a, 0x3fsizeof(a));
    scanf("%d"&n);
    while (scanf("%d%d"&x, &y)!=EOF) {
        if (x == -&& 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)13166 범죄 파티  (0) 2017.03.25
BOJ)3736 System Engineer  (0) 2017.03.25
BOJ)2660 회장뽑기  (0) 2017.03.23
BOJ)1755 숫자놀이  (0) 2017.03.23
BOJ)1747 소수&팰린드롬  (0) 2017.03.23
BOJ)10835 카드게임  (0) 2017.03.23
댓글
댓글쓰기 폼