(11409) 열혈강호 6

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

단계별로 풀어보기

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

 

 

 

최대 유량이 흐를 때 최소 비용이 아닌 최대 비용을 구해야 하는 문제. 어차피 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;
}