(11495) 격자 0 만들기

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

단계별로 풀어보기

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

 

 

 

인접한 정수 2개를 고르면 일반적으로 격자 총합에서 2를 감소시킬 수 있으나, 만약 어떤 양수의 상하좌우가 전부 0이라면 연산 한 번에 1만 감소하므로 손해를 보게 된다. 따라서 인접한 수를 최대한 많이 매칭해야 한다. 격자에서 인접한 칸을 고르는 문제는 보통 격자를 체스판으로 두고 푼다. 인접한 두칸을 고른다는 것은 체스판에서 항상 흰 칸과 검은 칸을 하나씩 고르는 것과 같기 때문이다.

격자를 위치에 따라 흰 칸과 검은 칸으로 구별한 뒤, 소스에서 흰 칸으로 각각의 칸에 처음 써진 숫자에 해당하는 최대 용량을 가진 간선을, 검은 칸에서 싱크로 각각의 칸에 처음 써진 숫자에 해당하는 최대 용량을 가진 간선을 긋고 모든 흰 칸마다 접근 가능한(이웃한) 검은 칸으로 무한대의 용량을 가진 간선을 잇는다. 소스에서 싱크로 유량이 흐르려면 항상 흰 칸과 검은 칸을 하나씩 지나야 하고, 이 두 칸에 연산을 행한 것과 같다. 이때 흐르는 최대 유량이 0 없이 두 개씩 짝지을 수 있는 수 쌍의 최대값이고 남은 숫자만큼 연산을 추가로 해야 하므로 정답은 격자의 숫자 총합에서 최대 유량을 뺀 값이다.

 

 

 

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

struct Edge;
const int s= 2501, e= 2502;
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 solve(){
  for(auto& elem:adj)  elem.clear();
  
  int n, m, tot= 0, res= 0;

  cin >> n >> m;
  
  for(int i=0;i<n;i++){
    for(int j=1;j<=m;j++){
      int x, pos= i*m+j;
      
      cin >> x;

      tot+= x;

      if((i+j)&1){
        addedge(s, pos, x);
        if(i>0)  addedge(pos, pos-m, INF);
        if(j>1)  addedge(pos, pos-1, INF);
        if(i<n-1)  addedge(pos, pos+m, INF);
        if(j<m)  addedge(pos, pos+1, INF);
      }else{
        addedge(pos, e, x);
      }
    }
  }
  
  while(leveling()){
    fill_n(work, SIZE, 0);
    
    while(1){
      int flow= dfs(s, INF);
      
      if(flow)  res+= flow;
      
      else  break;
    }
  }
  
  return tot-res;
}

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

  int T;
  
  cin >> T;
  
  while(T--){
    cout << solve() << "\n";
  }

  return 0;
}