[11493] 동전 교환

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

11493번: 동전 교환

---

#include <bits/stdc++.h>

using namespace std;

#ifdef ONLINE_JUDGE

constexpr bool local = false;

#else

constexpr bool local = true;

#endif

using ll = long long;

using pi = pair<ll, ll>;

constexpr int MAX_V = 1005;  // 최대 정점 개수

constexpr int S = 1001;      // 소스 정점 번호

constexpr int E = 1002;      // 싱크 정점 번호

constexpr int INF = 1'000'000'000;

int n, m, tar;

int c[MAX_V][MAX_V];     // 각 간선의 용량

int d[MAX_V][MAX_V];     // 각 간선의 비용

int f[MAX_V][MAX_V];     // 각 간선에 흐르는 중인 유량

vector<int> adj[MAX_V];  // 각 정점의 인접 리스트

int a[MAX_V];            // 정점의 색

int b[MAX_V];            // 동전의 색

void solve(void) {

    int ans = 0;

    int cnt = 0;

    // MCMF 시작

    while (1) {

        int prev[MAX_V], dst[MAX_V];

        bool inQ[MAX_V] = {0};  // 해당 정점이 큐 안에 있는가?

        queue<int> Q;

        memset(prev, -1, sizeof(prev));

        fill(dst, dst + MAX_V, INF);

        dst[S] = 0;

        inQ[S] = true;

        Q.push(S);

        while (!Q.empty()) {

            int curr = Q.front();

            Q.pop();

            inQ[curr] = false;  // 큐에서 꺼냄

            for (int next : adj[curr]) {

                // 최단 경로를 찾는 중이지만, 여전히 여유 용량 있어야 함

                if (c[curr][next] - f[curr][next] > 0 and

                    dst[next] > dst[curr] + d[curr][next]) {

                    dst[next] = dst[curr] + d[curr][next];

                    prev[next] = curr;

                    // 큐에 들어있지 않다면 큐에 넣음

                    if (!inQ[next]) {

                        Q.push(next);

                        inQ[next] = true;

                    }

                }

            }

        }

        if (prev[E] == -1) break;

        int flow = INF;

        for (int i = E; i != S; i = prev[i])

            flow = min(flow, c[prev[i]][i] - f[prev[i]][i]);

        cnt += flow;

        for (int i = E; i != S; i = prev[i]) {

            ans += (flow * d[prev[i]][i]);

            f[prev[i]][i] += flow;

            f[i][prev[i]] -= flow;

        }

    }

    // printf("%d %d\n", cnt, tar);

    cout << ans << '\n';

}

void init() {

    tar = 0;

    memset(c, 0, sizeof(c));

    memset(f, 0, sizeof(f));

    memset(d, 0, sizeof(d));

    memset(a, 0, sizeof(a));

    memset(b, 0, sizeof(b));

    for (int i = 0; i < MAX_V; i++) adj[i].clear();

}

int main(void) {

    if (!local) ios_base::sync_with_stdio(0), cin.tie(0);

    int t;

    cin >> t;

    while (t--) {

        init();

        cin >> n >> m;

        int i, j;

        for (i = 1; i <= m; i++) {

            int x, y;

            cin >> x >> y;

            adj[x].push_back(y);

            adj[y].push_back(x);

        }

        for (i = 1; i <= n; i++) cin >> a[i];

        for (i = 1; i <= n; i++) cin >> b[i];

        for (i = 1; i <= n; i++) {

            if (a[i] == 0 and b[i] == 1) {

                // 소스와 연결

                int x = S, y = i;

                adj[x].push_back(y);

                adj[y].push_back(x);

                c[x][y] = 1;

                tar++;

            }

        }

        for (i = 1; i <= n; i++) {

            if (a[i] == 1) {

                queue<int> q;

                // assert(q.empty());

                int dst[MAX_V];

                fill(dst, dst + MAX_V, INF);

                q.push(i);

                dst[i] = 0;

                while (!q.empty()) {

                    int cur = q.front();

                    q.pop();

                    for (int nxt : adj[cur]) {

                        if (1 <= nxt and nxt <= n)

                            ;

                        else

                            continue;

                        if (dst[nxt] == INF) {

                            dst[nxt] = dst[cur] + 1;

                            q.push(nxt);

                        }

                    }

                }

                for (j = 1; j <= n; j++) {

                    if (b[j] == 1) {

                        int x = j, y = i + 500, cost = dst[j];

                        // printf("(%d %d %d)\n", x, y, cost);

                        adj[x].push_back(y);

                        adj[y].push_back(x);

                        c[x][y] = INF;

                        d[x][y] = cost;

                        d[y][x] = -cost;

                    }

                }

            }

        }

        for (i = 1; i <= n; i++) {

            if (a[i] == 1 and b[i] == 0) {

                // 싱크와 연결

                int x = i + 500, y = E;

                adj[x].push_back(y);

                adj[y].push_back(x);

                c[x][y] = 1;

            }

        }

        solve();

    }

    return 0;

}

---