(2316) 도시 왕복하기 2

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

단계별로 풀어보기

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

 

 

 

네크워크 플로우 알고리즘은 간선의 최대 용량이 정해져 있을 때 쓸 수 있는 알고리즘인데 이 문제는 정점의 최대 용량이 1로 정해진 형태다. 이럴 땐 정점을 두 개로 쪼개면 된다. 한 번만 지나야 하는 정점을 들어오는 간선용 정점과 나가는 간선용 정점으로 나눈 뒤 들어오는 정점에서 나가는 정점으로 최대 유량 1의 간선을 만들면 된다.

 

 

 

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

struct Edge;
const int s= 2, e= 3;
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(2*u, 2*v-1, 1);
    addedge(2*v, 2*u-1, 1);
  }
  
  for(int i=3;i<=n;i++)  addedge(2*i-1, 2*i, 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;
}