BOJ 11378. 열혈강호 4

11378번: 열혈강호 4 (acmicpc.net)

solved.ac: Platinum III (2024.09.10)

 

문제에서 시키는 대로 모델링하고 맞을 수 있다.

모델링 방법이 조금씩 다른 것 같긴 하다. 본인은 다음과 같이 모델링했다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;
const int INF = 1e9;

vector<int> node[2005];
int capacity[2005][2005];
int flow[2005][2005];

int networkFlow(int source, int sink)
{
  int res = 0;
  int parent[2005];

  while(1)
    {
      memset(parent, -1, sizeof(parent));
      queue<int> q;
      parent[source] = source;
      q.push(source);

      while(!q.empty() && parent[sink] == -1)
        {
          int cur = q.front();
          q.pop();

          for(auto nxt: node[cur])
            {
              if(capacity[cur][nxt] > flow[cur][nxt] && parent[nxt] == -1)
              {
                parent[nxt] = cur;
                q.push(nxt);
              }
            }
        }
      if(parent[sink] == -1) break;

      int amount = INF;
      for(int cur = sink; cur != source; cur = parent[cur])
        {
          int prv = parent[cur];
          amount = min(amount, capacity[prv][cur] - flow[prv][cur]);
        }
      for(int cur = sink; cur != source; cur = parent[cur])
        {
          int prv = parent[cur];
          flow[prv][cur] += amount;
          flow[cur][prv] -= amount;
        }
      res += amount;
    }
  return res;
}

void addNode(int from, int to, int cap, bool is_inv = false)
{
  node[from].push_back(to);
  node[to].push_back(from);
  capacity[from][to] += cap;
  if(is_inv) capacity[to][from] += cap;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);

  int source = 2001, sink = 2002, punish = 2003;
  int n, m, k;
  cin >> n >> m >> k;

  addNode(source, punish, k);
  for(int i = 1; i <= n; i++)
    {
      addNode(source, i, 1);
      addNode(punish, i, k);
    }
  for(int i = 1; i <= m; i++) addNode(i + 1000, sink, 1);
  for(int i = 1; i <= n; i++)
    {
      int sz;
      cin >> sz;
      while(sz--)
        {
          int nxt;
          cin >> nxt;
          addNode(i, nxt + 1000, 1);
        }
    }
  cout << networkFlow(source, sink);
}