BOJ 17222 - 위스키 거래

BOJ 17222 - 위스키 거래

Maximum Flow 기본 문제이다.

문제를 잘읽고 구현해야 한다.

어떤 사람 $u$에게 들어가는 간선의 용량을 $g_u$ 로 설정해주면 된다.

const int inf = 2e9;
void solve() {
   int n, m;
   cin >> n >> m;

   int V = (n + m + 2);
   int source = n + m, sink = source + 1;
   vvi edges(V);
   vvi C(V, vi(V)), F(V, vi(V));

   vi get(n + m);
   fv(get);

   debug(get);

   for (int i = n; i < n + m; i++) {
      int k;
      cin >> k;
      vi to(k);
      fv(to);
      for (int &i: to) i--;

      for (int t: to) {
         edges[i].pb(t);
         edges[t].pb(i);
         C[i][t] = get[t];
         //C[t][i] = get[i];
      }
   }

   for (int i = 0; i < n; i++) {
      edges[i].pb(sink);
      C[i][sink] = inf;
   }
   for (int i = n; i < n + m; i++) {
      edges[source].pb(i);
      C[source][i] = get[i];
   }

   auto calc = [&]() {
      int ret = 0;
      while (1) {
         vi prev(V, -1);
         queue<int> q;
         q.push(source);
         prev[source] = source;
         while (sz(q)) {
            int cur = q.front();
            q.pop();
            for (int to: edges[cur]) {
               if (prev[to] == -1 && C[cur][to] - F[cur][to] > 0) {
                  prev[to] = cur;
                  q.push(to);
               }
            }
         }
         if (prev[sink] == -1) break;
         int mf = inf;
         for (int i = sink; i != source; i = prev[i]) mf = min(mf, C[prev[i]][i] - F[prev[i]][i]);
         for (int i = sink; i != source; i = prev[i]) F[prev[i]][i] += mf, F[i][prev[i]] -= mf;
         ret += mf;
      }
      return ret;
   };
   cout << calc();
}