제독

Problem link: https://www.acmicpc.net/problem/3640

정점을 분리하는 min-cost-max-flow 문제이다.

만약에, v에 도착하기 전에 같은 지점을 지나면 안된다는 조건이 없었다면(즉, 같은 간선만 안지나면 된다면), 풀이는 아래와 같이 매우 간단했을 것 이다.

1. 모든 간선에 용량 1을 준다.

2. 가상의 source를 만들고 source와 정점 1을 용량 2인 간선으로 연결한다.

3. 가상의 sink를 만들고 정점 v와 sink를 용량 2인 간선으로 연결한다.

4. mcmf를 푼다.

그런데, 위와 같은 풀이를 사용하면 같은 지점을 지나면 안된다는 조건을 만족할 수 없게 된다.

한 정점을 기준으로 아래와 같이 두 최단 경로가 교차하는 경우를 떠올려보면 반례가 쉽게 떠오른다.

# 용량 제한을 어기지 않았지만, 2개의 경로가 모두 x를 지나고 있다.

\     ^
\     |
\     |
\---> x --->
\     ^
\     |
\     |

이를 해결하기 위해서는 정점 x를 정점 x로 들어오는 정점 정점 x_i와 정점 x에서 나가는 정점 정점 x_o로 분리해준 뒤, (정점 x_i, 정점_o)에 용량 1을 주면 된다.

위의 예제를 재활용해서 정점을 분리해준다면, 아래와 같을 것이다.

눈여겨 볼 점은 이제 추가된 (정점 x_i, 정점 x_o)으로 인해 앞선 예제가 더 이상 용량 제한을 만족하지 못하게 되었다는 점이다.

\               ^
\               |
\               |
\---> x_i ---> x_o --->
\      ^
\      |
\      |

마지막으로 한 가지 주의할 점으로는 입력에 antiparallel한 edge가 존재할 수 있다는 점인데, 이에 대해선 아래 2가지 해법이 있을 수 있다.
이 문제에서는 1번 방법을 사용하였다.

1. adjacent_list + reverse edge pointing

2. isomorphic한 graph가 되도록 antiparallel에 대해 정점 추가하기

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <memory>

using namespace std;

struct Edge
{
  int source_;
  int destination_;
  int capacity_;
  int flow_;
  int cost_;
  Edge* reverse_;

  static void AddEdge(vector<vector<shared_ptr<Edge> > >& adjacent_list, const int source, const int destination,
                      const int capacity, const int cost)
  {
    Edge* forward = new Edge();
    Edge* reverse = new Edge();

    forward->source_ = source;
    forward->destination_ = destination;
    forward->capacity_ = capacity;
    forward->flow_ = 0;
    forward->cost_ = cost;

    reverse->source_ = destination;
    reverse->destination_ = source;
    reverse->capacity_ = 0;
    reverse->flow_ = 0;
    reverse->cost_ = -cost;

    forward->reverse_ = reverse;
    reverse->reverse_ = forward;

    adjacent_list[source].emplace_back(forward);
    adjacent_list[destination].emplace_back(reverse);
  }
};

static const int kMaxV = 1000;
static const int kMaxCost = 100;
static const int kMaxDistance = kMaxV * kMaxCost + 1;

int V, E;
vector<vector<shared_ptr<Edge> > > ADJACENT_LIST;

int Spfa(const int source, const int sink, vector<Edge*>& edges)
{
  edges.assign(2 * V, nullptr);

  vector<bool> is_queued(2 * V, false);
  vector<int> distances(2 * V, kMaxDistance);
  queue<int> q;

  is_queued[source] = true;
  distances[source] = 0;
  q.push(source);

  while (!q.empty())
  {
    int here = q.front();
    q.pop();

    is_queued[here] = false;

    for (const auto& edge : ADJACENT_LIST[here])
    {
      int there = edge->destination_;
      int residual = edge->capacity_ - edge->flow_;
      if (residual > 0 && distances[there] > distances[here] + edge->cost_)
      {
        distances[there] = distances[here] + edge->cost_;
        edges[there] = edge.get();
        if (!is_queued[there])
        {
          is_queued[there] = true;
          q.push(there);
        }
      }
    }
  }

  if (edges[sink] == nullptr)
  {
    return 0;
  }

  int min_residual = kMaxV;
  int current = sink;
  while (current != source)
  {
    min_residual = min(min_residual, edges[current]->capacity_ - edges[current]->flow_);
    current = edges[current]->source_;
  }

  return min_residual;
}

int Solve(const int source, const int sink)
{
  int ret = 0;

  while (true)
  {
    vector<Edge*> edges;
    const int min_residual = Spfa(source, sink, edges);

    if (min_residual == 0)
    {
      break;
    }

    int current = sink;
    while (current != source)
    {
      ret += min_residual * edges[current]->cost_;
      edges[current]->flow_ += min_residual;
      edges[current]->reverse_->flow_ -= min_residual;
      current = edges[current]->source_;
    }
  }

  return ret;
}

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  while (cin >> V >> E)
  {
    const int kSource = 0;
    const int kSink = 2 * V - 1;

    ADJACENT_LIST.assign(2 * V, vector<shared_ptr<Edge> >());

    Edge::AddEdge(ADJACENT_LIST, kSource, kSource + 1, 2, 0);
    Edge::AddEdge(ADJACENT_LIST, kSink - 1, kSink, 2, 0);

    for (int v = 1; v < V - 1; ++v)
    {
      int in = 2 * v;
      int out = in + 1;
      Edge::AddEdge(ADJACENT_LIST, in, out, 1, 0);
    }

    for (int it = 0; it < E; ++it)
    {
      int a, b, c;
      cin >> a >> b >> c;

      int out = 2 * (a - 1) + 1;
      int in = 2 * (b - 1);

      Edge::AddEdge(ADJACENT_LIST, out, in, 1, c);
    }

    cout << Solve(kSource, kSink) << "\n";
  }

  return 0;
}