[USACO] 백준 6156 - Cow Contest

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

 

힌트

어떤 소의 순서를 정확히 알기 위해선 자기보다 낮은 스킬의 소와 높은 스킬의 소의 합이 n - 1마리가 되어야 한다.

 

각 소들의 sparse 한 스킬 관계를 그래프 형태로 정리하는 방법을 생각해본다.

---

풀이

소의 순서를 확정하기 위해선 자기보다 높은 스킬의 소가 몇 마리인지, 자기보다 낮은 스킬의 소가 몇 마리인지 알아야 한다.

 

하지만 입력은 서로 두 소의 상하 관계만이 주어졌을 뿐이다.

 

파편화된 관계를 가지고 전체 순위를 알 수 있는 방법이 있을까?

 

사실 순위가 몇위인지 아는 건 딱히 중요하지 않고 순위가 있다는 것을 알아내기만 하면 된다.

 

각 관계를 높은 스킬의 소가 낮은 스킬의 소로 향하는 단방향 간선을 가진 그래프로 생각해보자.

 

그러면 각 소의 유불리 관계를 서로 이을 수 있고 모두 이었을 때 자신을 거치게 되는 소의 수와 다른 소로 향하는 수의 합이 n - 1개면 그 소의 순위는 결정될 수 있다.

 

관계를 잇는 것은 플로이드 워셜로 $O(N^{3})$의 시간 복잡도로 계산할 수 있으며 플로이드 워셜로 전체적인 소들의 관계를 계산한 후 각 소의 번호마다 루프를 돌면서 다른 소와 관계가 성립하는 경우를(그 소를 거쳐갈 수 있거나 자신을 거쳐오는 경우)를 더해 그 숫자가 n - 1이 되는 소를 카운팅 하여 출력하면 된다.

 

전체 코드

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int n, m;
int floyd[101][101];
int res;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> m;
  fill(&floyd[0][0], &floyd[0][0] + 101 * 101, 1e9);
  for (int i = 0; i < 101; ++i)
    floyd[i][i] = 0;
  
  for (int i = 0; i < m; ++i)
  {
    int go, to;
    cin >> go >> to;
    floyd[go][to] = 0;
  }

  for (int c = 1; c <= 100; ++c)
    for (int i = 1; i <= 100; ++i)
      for(int j = 1; j <= 100; ++j)
        floyd[i][j] = min(floyd[i][j], floyd[i][c] + floyd[c][j]);
  
  for (int i = 1; i <= 100; ++i)
  {
    int cnt = 0;
    for (int j = 1; j <= 100; ++j)
    {
      if (i == j) continue;
      if (!floyd[i][j] || !floyd[j][i])
        ++cnt;
    }

    if (cnt == n - 1)
      ++res;
  }

  cout << res;
}

제출 기록