(11378) 열혈강호 4

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

단계별로 풀어보기

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

 

 

 

네크워크 플로우는 특정 지점에서 다른 특정 지점으로 흐르는 최대 유량을 계산하는 알고리즘이다. 따라서 이렇게 여러 정점에서 흐르는 최대 유량을 구하고 싶을 땐, 여러 정점을 모두 잇는 가상의 시작, 도착 정점을 만들어서 풀면 된다.

가상의 시작 정점 s(2001)에서 벌점 유량 정점 s+1(2002)로 최대 유량 k의 간선을 만들고, 이 벌점 유량 정점에서 모든 직원에게 최대 유량 k의 간선을 만든다(의미적으로는 최대 유량 무한대가 맞지만 이미 s→s+1에서 가능한 최대 유량을 k로 제한했으므로 실제로는 똑같음). 그리고 직원마다 가능한 일에 최대 유량 1의 간선을 이어주고 모든 일을 종료 정점 e(2003)에 최대 유량 1의 간선으로 이어준다. 따라서 여러 직원이 같은 일을 해도 해당 일에서 종료 정점으로 유량은 1만 흐르게 되고 최대한 여러 일을 할 수 있는 경우를 탐색하게 된다.

이제 s에서 e로 흐르는 최대 유량은 s→s+1에 의해 벌점 k를 넘지 못하면서 직원에게 일을 할당할 수 있는 최대값과 같아졌다.

 

 

 

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

struct Edge;
const int s= 2001, e= 2003;
vector<Edge> adj[SIZE];
int level[SIZE], work[SIZE];

struct Edge{
  int to, cap, flux, rev;
  
  Edge(int to1, int cap1, int rev1): to(to1), cap(cap1), flux(0), rev(rev1){}

  int spare(){
    return cap-flux;
  }
};

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

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(Edge &edge: adj[now]){
      int next= edge.to;
      
      if(!level[next] && edge.spare()>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 &i= work[now];i<adj[now].size();i++){
    Edge &edge= adj[now][i];
    int next= edge.to;

    if(level[next]==level[now]+1 && edge.spare()>0){
      int flow= dfs(next, min(nowflow, edge.spare()));

      if(flow>0){
        adj[now][i].flux+= flow;
        adj[next][edge.rev].flux-= flow;
        
        return flow;
      }
    }
  }

  return 0;
}

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

  int n, m, k, ans= 0;

  cin >> n >> m >> k;
  
  addedge(s, s+1, k);
  
  for(int i=1;i<=n;i++){
    int t;
    
    cin >> t;
    
    addedge(s+1, i, k);
    addedge(s, i, 1);
    
    while(t--){
      int x;
      
      cin >> x;
      
      addedge(i, 1000+x, 1);
    }
  }
  
  for(int i=1;i<=m;i++)  addedge(1000+i, e, 1);
  
  while(leveling()){
    fill_n(work, SIZE, 0);
    
    while(1){
      int flow= dfs(s, INF);
      
      if(flow)  ans+= flow;
      
      else  break;
    }
  }

  cout << ans;

  return 0;
}