(17412) 도시 왕복하기 1

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

단계별로 풀어보기

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

 

 

네크워크 플로우는 특정 지점에서 다른 지점으로 흐르는 최대 유량을 구하는 알고리즘이다. 크게 세 가지로 나눌 수 있다.

 

포드-풀커슨 알고리즘은 DFS로 여유 용량이 있는 모든 간선에 최소 용량만큼 유량을 흘려보내는 과정을 반복한다. 코드가 짧고 직관적이지만 시간복잡도가 O(Ef)로 f(간선의 최대 유량)에 비례한다. 따라서 간선의 최대 유량이 큰 문제에는 부적합하다. 모든 간선의 최대 유량이 1이면 괜찮긴 한데 사실 이때는 디닉 알고리즘도 충분히 효율적이라 보통은 안 쓴다.

 

에드몬드-카프 알고리즘은 포드-풀커슨과 기본 원리는 같지만, DFS 대신 BFS를 사용해 간선 개수가 가장 적은 최단 경로부터 탐색해 유량도 그만큼 흘려준다. 시간 복잡도는 O(VE^2)로 시간 복잡도가 최대 유량의 영향을 받지 않아 안정적이다.

 

디닉 알고리즘은 현실적으로 PS에서 가능한 가장 좋은 플로우 알고리즘으로, BFS와 DFS를 모두 사용한다. 이전에 설명한 이분 매칭의 호프크로프트-카프 알고리즘과 비슷하다(정확히는 호프크로프트-카프가 디닉 알고리즘과 비슷한 것이다). 각 정점마다 BFS로 레벨 그래프를 만들어 최단 거리를 찾고 DFS로 유량을 흘려보내는 과정을 한 번에 하는 것이다. 시간 복잡도는 O(V^2E)인데, 여러 최적화 덕분에 실제로는 O(V√E)에 가깝게 동작한다(플로우 알고리즘은 복잡해서 저격 데이터를 만들기도 쉽지 않다).

 

또 간선을 어떻게 관리하느냐에 따라서도 크게 인접 배열과 인접 리스트+간선 구조체 두 가지로 나눌 수 있는데, 인접 배열은 간선마다 용량과 유량을 2차원 배열로 관리해 희소 그래프일수록 메모리 낭비가 심하다. 반대로 완전 그래프에 가까운 문제는 오히려 인접 배열이 유리하기도 하다. 인접 리스트는 간선에 도착점과 용량, 현재 유량을 저장하며 존재하는 간선만큼 메모리를 쓰므로 공간 복잡도가 O(V+E)로 줄어든다. 이때 역방향으로 유량을 흘려주기 위해 역방향 간선에 대한 정보를 저장해야 하는데, 초기에는 구조체 포인터를 썼지만 오버헤드나 간선 변경 시 생기는 문제 등이 있어 역방향 간선이 도착지를 시작으로 하는 정점의 배열에서 몇 번째 인덱스인지를 나타내는 정수 자료형을 저장하는 방식이 더 선호된다.

 

이 블로그에서 유량 관련 알고리즘의 개념이 간단하게 정리되어 있어 감을 잡을 때 꽤나 도움이 되었다.

 

 

 

포드 풀커슨 알고리즘+용량 인접배열

#include <iostream>
#include <algorithm>
#include <vector>
#define SIZE 401
#define INF 1000000001
using namespace std;

const int s= 1, e= 2;
int cap[SIZE][SIZE], flux[SIZE][SIZE];
vector<int> adj[SIZE];
int from[SIZE];

void dfs(int now){
  if(now==e)  return;

  for(int next: adj[now]){
    if(from[next])  continue;

    if(cap[now][next]-flux[now][next]>0){
      from[next]= now;
      dfs(next);
    }
  }

  return;
}

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

  int n, p, ans= 0;

  cin >> n >> p;
  
  while(p--){
    int u, v;
    
    cin >> u >> v;

    cap[u][v]++;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  while(1){
    fill_n(from, n+1, 0);

    dfs(s);

    if(!from[e])  break;

    int flow= INF;
    
    for(int i=e;i!=s;i=from[i]){
      flow= min(flow, cap[from[i]][i]-flux[from[i]][i]);
    }
    
    for(int i=e;i!=s;i=from[i]){
      flux[from[i]][i]+= flow;
      flux[i][from[i]]-= flow;
    }
    
    ans+= flow;
  }

  cout << ans;

  return 0;
}

 

 

 

에드몬드 카프 알고리즘+용량 인접배열

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define SIZE 401
#define INF 1000000001
using namespace std;

const int s= 1, e= 2;
int cap[SIZE][SIZE]= {}, flux[SIZE][SIZE]= {};
vector<int> adj[SIZE];
int from[SIZE];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, p, ans =0;

  cin >> n >> p;
  
  while(p--){
    int u, v;
    
    cin >> u >> v;

    cap[u][v]++;
    adj[u].push_back(v);
    adj[v].push_back(u);
  }
  
  while(1){
    fill_n(from, n+1, 0);
    queue<int> q;
    q.push(s);

    while(!q.empty() && !from[e]){
      int now= q.front();
      q.pop();

      for(int next: adj[now]){
        if(from[next])  continue;

        if(cap[now][next]-flux[now][next]>0){
          from[next]= now;
          q.push(next);

          if(next==e)  break;
        }
      }
    }

    if(!from[e])  break;

    int flow= INF;
    
    for(int i=e;i!=s;i=from[i]){
      flow= min(flow, cap[from[i]][i]-flux[from[i]][i]);
    }
    
    for(int i=e;i!=s;i=from[i]){
      flux[from[i]][i]+= flow;
      flux[i][from[i]]-= flow;
    }
    
    ans+= flow;
  }

  cout << ans;

  return 0;
}

 

 

 

디닉 알고리즘 + 용량 구조체(역방향 간선 인덱스(정수형)으로 관리)

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define SIZE 401
#define INF 1000000001
using namespace std;

struct Edge;
const int s= 1, e= 2;
vector<Edge> adj[SIZE];
int level[SIZE], work[SIZE];

struct Edge{
  int to, cap, flux, rev;
  
  Edge(int to1, int cap1, int rev1): to(to1), cap(cap1), flux(0), rev(rev1){}

  int spare(){
    return cap-flux;
  }
};

void addedge(int u, int v, int capacity){
  int uidx= adj[u].size();
  int vidx= adj[v].size();
  
  adj[u].push_back(Edge(v, capacity, vidx));
  adj[v].push_back(Edge(u, 0, uidx));
}

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(Edge &edge: adj[now]){
      int next= edge.to;
      
      if(!level[next] && edge.spare()>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 &i= work[now];i<adj[now].size();i++){
    Edge &edge= adj[now][i];
    int next= edge.to;

    if(level[next]==level[now]+1 && edge.spare()>0){
      int flow= dfs(next, min(nowflow, edge.spare()));

      if(flow>0){
        adj[now][i].flux+= flow;
        adj[next][edge.rev].flux-= flow;
        
        return flow;
      }
    }
  }

  return 0;
}

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

  int n, p, ans= 0;

  cin >> n >> p;
  
  for(int i=0;i<p;i++){
    int u, v;
    
    cin >> u >> v;

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

  cout << ans;

  return 0;
}