(11111) 두부장수 장홍준 2

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

단계별로 풀어보기

55단계(네크워크 플로우 2) 4번째

 

 

 

브로큰 프로파일 DP로 풀었던 문제의 범위가 커져서 돌아왔다.

이전에 말했듯이 이웃한 두 칸을 고르는 문제는 체스판처럼 생각하고 한쪽 색을 소스에, 한쪽 색을 싱크에 연결하면 된다고 했다.

인접한 이웃 칸이 있다면, 해당 칸으로 최대 용량 1, 가중치는 해당 두 칸의 두부 등급에 해당하는 두부값을 주면 된다. 단 어떤 두부는 한 칸짜리 두부로 만들어서 버리는 경우가 이득일 수도 있으므로, 소스와 연결된 색에서 바로 싱크로 최대 용량 1, 가중치 0짜리 간선을 이어준다.

이대로 MCMF를 돌리면 되는데, 문제에서 요구하는 건 최소값이 아닌 최대값이다. 따라서 가중치의 부호를 바꿔 간선을 만들어줘야 한다.

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

int price[5][5]={{10,8,7,5,1},{8,6,4,3,1},{7,4,3,2,1},{5,3,2,2,1},{1,1,1,1,0}};

struct Edge;
const int s= 2501, e= 2502;
vector<Edge> adj[SIZE];

struct Edge{
  int to, cap, flux, cost, rev;
  bool onedir;
  
  Edge(int to1, int cap1, int cost1, int rev1, bool onedir1=true):
    to(to1), cap(cap1), flux(0), cost(cost1), rev(rev1), onedir(onedir1) {}
  
  int spare(){
    return cap-flux;
  }
};

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

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

  int n, m, res_flow= 0, res_cost= 0;

  cin >> n >> m;
  
  vector<vector<int> > tofu(n, vector<int> (m));

  for(int i=0;i<n;i++){
    string str;
    
    cin >> str;

    for(int j=0;j<m;j++){
      if(str[j]=='F')  tofu[i][j]= 4;
      else if(str[j]=='D')  tofu[i][j]= 3;
      else if(str[j]=='C')  tofu[i][j]= 2;
      else if(str[j]=='B')  tofu[i][j]= 1;
    }
  }
  
  for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      int x= i*m+j+1;

      if((i+j)&1){
        addedge(s, x, 1);
        addedge(x, e, 1);
        if(i>0)  addedge(x, x-m, 1, -price[tofu[i][j]][tofu[i-1][j]]);
        if(i<n-1)  addedge(x, x+m, 1, -price[tofu[i][j]][tofu[i+1][j]]);
        if(j>0)  addedge(x, x-1, 1, -price[tofu[i][j]][tofu[i][j-1]]);
        if(j<m-1)  addedge(x, x+1, 1, -price[tofu[i][j]][tofu[i][j+1]]);
      }else{
        addedge(x, e, 1);
      }
    }
  }
  
  while(1){
    int from[SIZE]= {}, edgeidx[SIZE]= {}, dist[SIZE];
    bool inq[SIZE]= {};
    fill_n(dist, SIZE, INF);
    queue<int> q;

    dist[s]= 0;
    inq[s]= true;
    q.push(s);

    while(!q.empty()){
      int now= q.front();
      inq[now]= false;
      q.pop();

      for(int i=0;i<adj[now].size();i++){
        Edge &edge= adj[now][i];
        int next= edge.to;

        if(edge.spare()>0 && dist[next]>dist[now]+edge.cost){
          dist[next]= dist[now]+edge.cost;
          from[next]= now;
          edgeidx[next]= i;
          
          if(!inq[next]){
            inq[next]= true;
            q.push(next);
          }
        }
      }
    }

    if(!from[e])  break;
    
    int flow= INF;
    for(int i=e;i!=s;i=from[i])  flow= min(flow, adj[from[i]][edgeidx[i]].spare());

    for(int i=e;i!=s;i=from[i]){
      Edge &edge= adj[from[i]][edgeidx[i]];
      
      res_cost+= flow*edge.cost;
      
      edge.flux+= flow;
      adj[i][edge.rev].flux-= flow;
    }
    
    res_flow++;
  }

  cout << -res_cost;

  return 0;
}