(13161) 분단의 슬픔

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

단계별로 풀어보기

54단계(네크워크 플로우 1) 5번째

 

 

 

에드몬드-카프로도 시간 초과가 나서 디닉 알고리즘을 써야 하는 문제.

A진영을 시작점, B진영을 도착점으로 두면 그룹을 두 진영으로 나누는 것은 연결된 간선들을 자르는 것과 같고, 이때 간선들의 용량 합(슬픔의 합)을 최소로 만드는 것이 목표다. 최소 컷은 최대 유량과 같다는 것이 증명되어 있다.

무조건 A진영 혹은 B진영에 가야 하는 사람은 각각 A진영, B진영과 용량이 무한대인 간선으로 잇는다. 사람 i와 j가 떨어질 때 슬픈 정도를 사람에 해당하는 정점 사이 간선의 용량으로 정한다. 간선이 잘려 두 사람이 떨어질 때 이 간선의 용량이 슬픔이 된다.

최대 유량을 흘려보내고 나면 최소 컷에 해당하는 간선은 잔여 용량이 0이 되므로, s에서 BFS를 돌려 갈 수 있는 정점을 찾는다. 이 정점에 해당하는 사람이 A진영 사람이 되고 방문하지 못한 정점에 해당하는 사람이 B진영 사람이 된다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define SIZE 503
#define INF 1000000
using namespace std;

const int s= 501, e= 502;
int cap[SIZE][SIZE], flux[SIZE][SIZE];
int level[SIZE], work[SIZE];

bool leveling(){
  queue<int> q;
  fill_n(level, SIZE, 0);

  level[s]= 1;
  q.push(s);

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

    for(int next=1;next<=e;next++){
      if(!level[next] && cap[now][next]-flux[now][next]>0){
        level[next]= level[now]+1;
        q.push(next);
      }
    }
  }

  return level[e];
}

int dfs(int now, int nowflow){
  if(now==e)  return nowflow;

  for(int &next= work[now];next<=e;next++){
    if(level[next]==level[now]+1 && cap[now][next]-flux[now][next]>0){
      int flow= dfs(next, min(nowflow, cap[now][next]-flux[now][next]));

      if(flow>0){
        flux[now][next]+= flow;
        flux[next][now]-= flow;
        return flow;
      }
    }
  }

  return 0;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int n;
  cin >> n;

  for(int i=1;i<=n;i++){
    int t;
    cin >> t;

    if(t==1)  cap[s][i]= INF;
    else if(t==2)  cap[i][e]= INF;
  }

  for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
      cin >> cap[i][j];
    }
  }

  int total= 0;
  while(leveling()){
    fill_n(work, SIZE, 0);
    while(1){
      int flow= dfs(s, INF);
      if(flow)  total+= flow;
      else  break;
    }
  }

  cout << total << "\n";

  queue<int> q;
  bool visited[SIZE]= {};

  visited[s]= true;
  q.push(s);

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

    for(int next=1;next<=e;next++){
      if(!visited[next] && cap[now][next]-flux[now][next]>0){
        visited[next]= true;
        q.push(next);
      }
    }
  }

  for(int i=1;i<=n;i++){
    if(visited[i])  cout << i << " ";
  }
  cout << "\n";
  for(int i=1;i<=n;i++){
    if(!visited[i])  cout << i << " ";
  }
  cout << "\n";

  return 0;
}