[10159번] 저울

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

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

이 문제는 플로이드 워셜 알고리즘으로 접근 할 수 있다.

일단 N제한이 100이고, 각각 무게에 대한 상대적인 지표가 입력을 통해 나타난다.

이것을 이용하여 그래프를 형성해주고, 간선의 가중치를 1이라 생각한 후, 최단 거리가 갱신된다면, 그 정점과 다른 정점은 비교 결과를 알 수 있다는 의미가 된다.

따라서 x->y로 갈 때 최단 거리가 갱신되지 않은 것들은 비교 결과를 알 수 없는 것인 것이라고 판단 할 수 있다.  

소스 코드 : 

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

#include <iostream> #include <cstdio>   #define INF 987654321 #define min(a,b)(a < b ? a : b) using namespace std;   int adj[101][101]; int dist[101][101]; int cnt[101];   int main() {     int V, E;     scanf("%d %d", &V, &E);       for (int i = 1; i <= V; i++)         for (int j = 1; j <= V; j++)             i == j ? adj[i][j] = 0 : adj[i][j] = INF;       for (int i = 0; i < E; i++)     {         int from, to;         scanf("%d %d", &from, &to);         adj[from][to] = 1;     }       for (int k = 1; k <= V; k++)         for (int x = 1; x <= V; x++)             for (int y = 1; y <= V; 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 <= V; i++)     {         for (int j = 1; j <= V; j++)             if (0 <= adj[i][j] && adj[i][j] < INF)             {                 cnt[i]++;                 cnt[j]++;             }     }       for (int i = 1; i <= V; i++)         printf("%d\n", V - (cnt[i] - 1));       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus