(11408) 열혈강호 5

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

단계별로 풀어보기

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

 

 

 

이제 간선에 최대 용량 뿐만 아니라 비용까지 생겨, 최대 유량을 흘리면서도 그 비용을 최소화해야 하는 문제를 MCMF(Minimum Cost Maximum Flow)라고 한다. 기존의 에드몬드-카프 알고리즘은 단순히 BFS를 이용해 DAG를 찾았지만 MCMF는 최단 경로 알고리즘을 써서 길을 찾아야 한다. 이때 역방향 간선은 흘린 유량을 다시 취소한다는 의미인데, 더해줬던 비용을 빼주려면 비용의 부호가 반대여야 하므로 일반적으로 음수 가중치 간선이 생기기 때문에 다익스트라 대신 벨만 포드 알고리즘을 사용해야 한다. 하지만 벨만 포드 알고리즘은 O(VE)로 시간복잡도가 크기 때문에 큐를 이용해 시간복잡도를 O(V+E)로 개선한 SPFA를 사용한다. SPFA로 DAG를 찾은 뒤에는 에드몬드-카프 알고리즘처럼 유량을 흘려주면 된다.

SPFA 대신 포텐셜을 사용한 다익스트라(포텐셜을 사용하면 음수 간선에도 사용 가능하며, 벨만 포드보다는 다익스트라가 더 빠르다.)를 돌리거나, 에드몬드 카프 알고리즘 대신 디닉 알고리즘 방식으로 유량을 흘리는 zkw MCMF로 최적화가 가능하다.

 

 

 

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

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

struct Edge{
  int to, cap, flux, cost, rev;
  
  Edge(int to1, int cap1, int cost1, int rev1): to(to1), cap(cap1), flux(0), cost(cost1), rev(rev1){}
  
  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;
  for(int i=1;i<=n;i++){
    int x;
    
    cin >> x;

    while(x--){
      int v, c;
      
      cin >> v >> c;

      v+= sz;

      addedge(i, v, INF, c);
    }
  }

  for(int i=1;i<=n;i++)  addedge(s, i, 1);
  for(int i=sz+1;i<=sz+m;i++)  addedge(i, 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;

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

  cout << res_flow << "\n" << res_cost;

  return 0;
}