[2660번] 회장 뽑기

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 플로이드 워셜 알고리즘

사람들간의 관계를 그래프로 구성하고 가중치를 1로 둔 후

n제한이 50이기에 플로이드 워셜 알고리즘을 이용하여 문제를 해결 할 수 있다.

소스 코드 : 

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 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

#include <iostream> #include <cstdio> #include <vector> #include <memory.h> #include <algorithm>   using namespace std;   const int INF = 978654312;   vector<int> vc[62]; int adj[52][52];   int main() {     int n;     scanf("%d", &n);       for (int i = 0; i <= 50; i++)         for (int j = 0; j <= 50; j++)             if (i != j)                 adj[i][j] = INF;       while (1)     {         int from, to;         scanf("%d %d", &from, &to);           if (from == -1)             break;           adj[from][to] = 1;         adj[to][from] = 1;     }       for (int k = 1; k <= n; k++)         for (int x = 1; x <= n; x++)             for (int y = 1; y <= n; y++)                 if (adj[x][y] > adj[x][k] + adj[k][y])                     adj[x][y] = adj[x][k] + adj[k][y];       for (int i = 1; i <= n; i++)     {         int maxVal = -1;         for (int j = 1; j <= n; j++)         {             if (i == j)                 continue;               maxVal = max(maxVal, adj[i][j]);         }           vc[maxVal].push_back(i);     }          for(int i = 1; i <= n; i++)         if (vc[i].size())         {             printf("%d %d\n", i, vc[i].size());             for (int j = 0; j < vc[i].size(); j++)                 printf("%d ", vc[i][j]);               break;         }     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus