6241 - Dining

문제 링크

---

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

문제 요약

---

\(N\)마리의 소와 \(F\)개의 음식, \(D\)개의 음료가 주어진다. 각각의 소들은 식성이 다 다르기 때문에 좋아하는 음료, 음식들이 전부 다 다르다. 소들은 자신이 좋아하는 음식들 중 한개와 자신이 좋아하는 음료들 중 한개를 동시에 먹을 때 행복하다고 느낀다. 모든 음식과 음료들은 한 소에게만 나눠줄 수 있을 때 행복한 소의 수를 최대로 만드는 문제다.

문제 풀이

---

얼핏 보면 이분 매칭과 흡사해 보일 수 있다. 하지만 이 문제는 소에게 음료와 음식을 동시에 할당해 줘야 하기때문에 이분 매칭으로는 풀 수 없다. 그렇다면 조금은 다른 풀이를 생각해야 한다.

이 문제에서는 소를 정 중앙에 두고 왼쪽에는 음식, 오른쪽에는 음료를 두고(음식과 음료가 바뀌어도 상관없다) 그래프를 만들어 줘야 한다. 그렇게 소스, 음식, 소, 음료, 싱크 순으로 유량이 흘러가게 해준다면 자연스럽게 소는 한개의 음료와 한개의 음식에 매칭이 될 것이고 행복한 소가 가장 많게 되는 경우는 최대 유량을 구한 경우가 될 것이다. 이를 그림으로 표현한다면 아래와 같다.

이 그래프에서 모든 간선의 \(capacity\)는 1이란 것에 주의해야 한다. 또 가장 중요한 것중 하나가 소들은 정점 분할을 해 줘야 한다는 것이다. 만약 소들의 정점을 분할하지 않고 그대로 사용하면 한마리의 소를 통해서 여러 음식과 음료가 선택이 되고 한 마리의 소가 두 마리의 행복한 소를 생산해 내는 엄청난 일이 벌어진다. 따라서 꼭 소를 통해서 흐르는 유량은 1이 되도록 정점 분할을 해 줘야 한다.

소스 코드

---

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
struct Edge {
  int opp, cap, rev;
  Edge(int opp, int cap, int rev) : opp(opp), cap(cap), rev(rev) {}
};
 
const int INF = 987654321;
int n, f, d, N, x, y, z, src, sink;
vector<int> dist, iter;
vector< vector<Edge> > node;
 
inline int getCowFood(int idx) {
  return f + d + idx;
}
 
inline int getCowDrink(int idx) {
  return f + d + n + idx;
}
 
inline int getFood(int idx) {
  return idx;
}
 
inline int getDrink(int idx) {
  return f + idx;
}
 
void addEdge(int here, int there, int cap) {
  node[here].push_back(Edge(there, cap, (int)node[there].size()));
  node[there].push_back(Edge(here, 0, (int)node[here].size() - 1));
}
 
bool bfs() {
  dist.assign(N, -1);
  queue<int> q;
  q.push(src);
  dist[src] = 0;
   
  while (!q.empty()) {
    int here = q.front();
    q.pop();
     
    for (int i = 0 ; i < node[here].size() ; ++i) {
      int there = node[here][i].opp;
      int cap = node[here][i].cap;
       
      if (cap && dist[there] == -1) {
        dist[there] = dist[here] + 1;
        q.push(there);
      }
    }
  }
   
  return dist[sink] != -1;
}
 
int dfs(int here, int flow) {
  if (here == sink) {
    return flow;
  }
   
  for (int& i = iter[here] ; i < node[here].size() ; ++i) {
    int there = node[here][i].opp;
    int cap = node[here][i].cap;
     
    if (cap && dist[here] < dist[there]) {
      int minFlow = dfs(there, min(flow, cap));
      if (minFlow) {
        node[here][i].cap -= minFlow;
        node[there][node[here][i].rev].cap += minFlow;
        return minFlow;
      }
    }
  }
   
  return 0;
}
 
int maxFlow() {
  int ret = 0;
  while (bfs()) {
    iter.assign(N, 0);
    int flow;
    while ((flow = dfs(src, INF))) {
      ret += flow;
    }
  }
  return ret;
}
 
int main() {
  scanf("%d%d%d", &n, &f, &d);
  N = n + n + f + d + 2;
  src = n + n + f + d;
  sink = n + n + f + d + 1;
   
  node.resize(N);
  for (int i = 0 ; i < f ; ++i) {
    addEdge(src, getFood(i), 1);
  }
  for (int i = 0 ; i < d ; ++i) {
    addEdge(getDrink(i), sink, 1);
  }
  for (int i = 0 ; i < n ; ++i) {
    addEdge(getCowFood(i), getCowDrink(i), 1);
  }
 
  for (int i = 0 ; i < n ; ++i) {
    scanf("%d%d", &x, &y);
    while (x--) {
      scanf("%d", &z);
      --z;
      addEdge(getFood(z), getCowFood(i), 1);
    }
    while (y--) {
      scanf("%d", &z);
      --z;
      addEdge(getCowDrink(i), getDrink(z), 1);
    }
  }
   
  printf("%d\n", maxFlow());
}