(1420) 학교 가지마!

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

단계별로 풀어보기

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

 

 

 

간선이 아닌 정점에 대한 최소 컷을 구해야 하는 문제. 최소 컷이 최대 유량과 같다는 것은 분단의 슬픔에서 언급했고, 정점을 간선으로 변환하는 방법은 도시 왕복하기 2에서 언급했다.

 

 

 

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

struct Edge;
int s, e;
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, m, sx, sy, ex, ey, ans= 0;

  cin >> n >> m;
  
  vector city(n, vector<bool> (m));
  
  for(int i=0;i<n;i++){
    string str;
    
    cin >> str;

    for(int j=0;j<m;j++){
      if(str[j]=='#'){
        city[i][j]= true;
      }else if(str[j]=='K'){
        s= 2*(i*m+j+1);
        sy= i;  sx= j;
      }else if(str[j]=='H'){
        e= 2*(i*m+j+1)-1;
        ey= i;  ex= j;
      }
    }
  }
  
  if(abs(sy-ey)+abs(sx-ex)==1){
    cout << -1;
    
    return 0;
  }
  
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(city[i][j])  continue;

      int x= i*m+j+1;

      if(i<n-1 && !city[i+1][j]){
        addedge(2*x, 2*(x+m)-1, 1);
        addedge(2*(x+m), 2*x-1, 1);
      }
      if(j<m-1 && !city[i][j+1]){
        addedge(2*x, 2*(x+1)-1, 1);
        addedge(2*(x+1), 2*x-1, 1);
      }
    }
  }
  
  for(int i=1;i<=n*m;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;
}