(11493) 동전 교환

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

단계별로 풀어보기

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

 

 

 

MCMF에서 양방향 그래프인 경우, 단방향 간선이 각각 이어져 있다고 생각할 수 있다. 하지만 이렇게 하면 하나의 무방향 간선 당 두 개의 단방향 간선에 역방향 간선까지 무려 4개나 만들어야 한다. 대신 간선 하나로 해결할 수 있는 방법이 있다. 간선을 하나만 만들어 유량이 양수일 땐 그대로, 유량이 음수일 땐 역방향 간선을 정방향으로, 지금 간선을 역방향 간선으로 바꿔주면 된다(원래 간선의 가중치를 저장한 뒤 정방향 간선은 그대로, 역방향 간선은 부호를 바꿔주면 된다). 유량이 0이라면 둘 다 정방향 간선으로 취급해 먼저 오는 쪽을 적용해주면 된다. 단 소스에서 나오는 간선이나 싱크로 들어가는 간선은 단방향으로 설정해야 하는 경우가 많으므로 일반적인 단방향 간선도 별개로 구현해야 한다.

간선 구현을 끝냈다면 색 하나를 잡고 해당 색의 동전을 소스로부터 잇고, 해당 색의 정점을 싱크로 이어주면 최대 유량이 흐르는 것은 모든 동전이 맞는 색을 찾아가는 것을 의미하고, 최소 비용은 이때 교환 횟수를 최소로 만드는 것을 의미한다.

 

 

 

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

struct Edge;
const int s= 501, e= 502;
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, bool isonedir= true){
  int uidx= adj[u].size();
  int vidx= adj[v].size();
  
  adj[u].push_back(Edge(v, capacity, cost, vidx, isonedir));
  if(isonedir)  adj[v].push_back(Edge(u, 0, -cost, uidx, true));
  else  adj[v].push_back(Edge(u, capacity, cost, uidx, false));
}

int solve(){
  for(auto& elem:adj)  elem.clear();

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

  cin >> n >> m;
  
  while(m--){
    int u, v;
    
    cin >> u >> v;

    addedge(u, v, INF, 1, false);
  }

  for(int i=1;i<=n;i++){
    int b;
    
    cin >> b;
    
    if(b)  addedge(i, e, 1);
  }
  for(int i=1;i<=n;i++){
    int b;
    
    cin >> b;
    
    if(b)  addedge(s, i, 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]];
      Edge &edgerev= adj[i][edge.rev];
      
      res_cost+= flow*edge.cost;
      
      edge.flux+= flow;
      edgerev.flux-= flow;
      
      if(!edge.onedir){
        if(edge.flux>0){
          edge.cost= abs(edge.cost);
          edgerev.cost= -abs(edgerev.cost);
        }else if(edge.flux<0){
          edge.cost= -abs(edge.cost);
          edgerev.cost= abs(edgerev.cost);
        }else{
          edge.cost= abs(edge.cost);
          edgerev.cost= abs(edgerev.cost);
        }
      }
    }
    
    res_flow+= flow;
  }

  return res_cost;
}

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