(2365) 숫자판 만들기

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

단계별로 풀어보기

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

 

 

 

행과 열을 각각 정점으로 보면 어떤 칸은 행과 열을 잇는 간선, 칸에 들어가는 숫자는 흐르는 유량으로 볼 수 있다. 가상의 시작 정점에서 모든 행에 각각의 행이 가져야 하는 숫자의 합을 최대 용량으로 갖는 간선을, 모든 열에서 가상의 도착 정점으로 각각의 열이 가져야 하는 숫자의 합을 최대 용량으로 갖는 간선을 잇고 네크워크 플로우를 돌려 최대 유량이 모든 행의 합(당연히 모든 열의 합과도 같아야 한다.)과 같으면 숫자판을 채우는 경우가 존재한다. 다만 가능한 입력만 주어진다 했으므로 여기서는 생각하지 않아도 된다.

문제는 가능한 숫자 범위의 최소값을 묻고 있다. 칸에 들어가는 숫자를 흐르는 유량으로 볼 수 있다고 했으므로, 정답이 a라면 모든 간선의 최대 용량을 a로 설정해도 행의 합만큼 최대 유량이 흐른다. 따라서 모든 간선의 최대 용량을 x로 제한했을 때 흐르는 최대 유량이 행의 합과 같은가? 를 결정함수로 두고 이분 탐색으로 답을 찾으면 된다. 하나의 행이나 열이 갖는 합의 최대가 10000이므로 네크워크 플로우를 log(10000)번 돌리면 정답을 찾을 수 있다.

마지막에는 정답이 되는 숫자판도 출력해야 하는데, 정답인 최대 용량 상태로 다시 플로우를 돌려 각각의 간선에 흐르는 유량이 해당 칸에 들어가는 숫자가 된다.

 

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define SIZE 103
#define INF 100000
using namespace std;

const int s= 101, e= 102;
int cap[SIZE][SIZE], flux[SIZE][SIZE];
int level[SIZE], work[SIZE];
int n, tot= 0;

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;
}

bool dinic(int c){
  fill_n(flux[0], SIZE*SIZE, 0);
  
  for(int i=1;i<=n;i++){
    for(int j=n+1;j<=2*n;j++){
      cap[i][j]= c;
    }
  }

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

  return (res==tot);
}

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

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

    tot+= t;
    cap[s][i]= t;
  }
  for(int i=n+1;i<=2*n;i++){
    int t;
    
    cin >> t;

    cap[i][e]= t;
  }

  int lo= -1, hi= 10000;
  while(lo+1<hi){
    int mid= (lo+hi)/2;
    
    (dinic(mid) ? hi : lo)= mid;
  }

  cout << hi << "\n";
  
  dinic(hi);
  
  for(int i=1;i<=n;i++){
    for(int j=n+1;j<=2*n;j++){
      cout << flux[i][j] << " ";
    }
    cout << "\n";
  }

  return 0;
}