BOJ 12963. 달리기

12963번: 달리기 (acmicpc.net)

solved.ac: Platinum 3 (2024.09.06)

 

플로우 안 쓰는 플로우 문제입니다.

일단 문제를 딱 보자마자 최대 유량 문제구나를 파악할 수 있는데 범위가 노답입니다.

 

최대 유량을 구하는 문제이므로 최소 컷을 구해야 함을 알 수 있습니다.

이때 용량이 특수하게 주어지므로, 다음을 이용합시다.

1. 최대 유량을 흘렸을 때, 유량이 존재하는 간선을 모두 제거하면 보낼 수 있는 유량은 0이다.
2. i번 간선에 유량이 흐른다면 이 유량으로 0번부터 i-1번 간선에 모두 유량을 보낼 수 있다.

 

0번 간선에서 N-1번 간선까지의 어떠한 경로가 존재한다면, 유량은 당연히 가장 작은 간선의 용량이 될 것입니다.

또한 2번에 의해, 여러 개의 경로가 존재할 때 일부 간선이 겹쳐도 전혀 문제될 게 없습니다.

 

만약 모든 간선을 연결해도 두 정점이 연결되지 않는다면, 당연히 유량은 0입니다.

이제 어떠한 간선이 있고, 해당 간선을 연결하면 0번과 N-1번 정점이 연결된다고 가정해 보겠습니다.

그래프 상에서 현재 최소 용량 간선은 연결되어 있지 않다고 가정해 보겠습니다.

그렇다면 0번 정점과 N-1번 정점을 잇는 또 다른 경로를 찾았다고 하면, 다음과 같이 일반화가 가능합니다.

만약 색칠된 간선의 용량이 가장 작고, a에 충분히 보내도 될 만큼의 유량이 흐른다면,

전체 유량은 이전에 미리 빼두었던 간선의 용량과 현재 칠해진 간선의 유량의 합이 됩니다.

 

충분히 보내도 될 만큼의 유량이 흐른다, 이는 위의 2번 정리를 이용하면 될 것 같습니다.

아래 그림에서 빨간색 간선의 용량이 파란색 간선의 용량보다 크다면, 빨간색 간선을 통해 흘린 유량은 두 파란 간선에 모두 흘리고도 남습니다.

다음으로 어떠한 간선으로 연결을 시도했을 때 두 정점이 연결이 된다. 이때 용량은 가장 작아야 한다.

잠깐만 생각해보면 그냥 간선 용량을 큰 것부터 연결해 보면 됨을 알 수 있습니다. 이렇게 구성하면 충분히 보내도 될 만큼의 유량이 흐르는 것도 자연스럽게 만들어지게 됩니다.

 

어떤 간선을 연결했을 때 0번 정점과 N-1번 정점이 연결되는가?

이는 분리 집합 자료구조를 이용하면 알 수 있습니다.

 

확인하려는 간선이 잇는 두 정점을 p, q라 하면,

(0과 p, q와 n-1이 연결되어 있다) or (0과 q, p와 n-1이 연결되어 있다) 를 만족시키면 연결되는 간선임을 알 수 있습니다.

 

구현은 꽤나 간단합니다.

#include <iostream>
#include <vector>

using namespace std;
typedef long long int LL;
const LL mod = 1e9+7;

/* Disjoint Set */
int parent[2001];

void init()
{
  for(int i = 0; i < 2001; i++) parent[i] = i;
}

int find(int x)
{
  if(parent[x] == x) return x;
  else return parent[x] = find(parent[x]);
}

void merge(int p, int q)
{
  p = find(p);
  q = find(q);
  if(p != q) parent[q] = p;
}

struct edge
{
LL cost;
int p, q;
};

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int n, m;
  cin >> n >> m;

  vector<edge> edges;
  init();

  LL cur = 1;
  for(int i = 0; i < m; i++)
    {
      int p, q;
      cin >> p >> q;
      edges.push_back({cur, p, q});
      cur = (cur * 3) % mod;
    }

  LL res = 0;
  for(int i = m - 1; i >= 0; i--)
    {
      LL cost = edges[i].cost;
      LL p = edges[i].p, q = edges[i].q;

      if((find(p) == find(0) && find(q) == find(n - 1)) || (find(p) == find(n - 1) && find(q) == find(0)))
      {
        res = (res + cost) % mod;
      }
      else merge(p, q);
    }
  cout << res;
}