Network FLow 최대 유량 알고리즘

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

6086번: 최대 유량

 

 

#include <bits/stdc++.h>
#include <unordered_set>

#define MAX 800
#define INF 1e9;

using namespace std;

int n, res;
int c[MAX][MAX], f[MAX][MAX], d[MAX];
vector<int> adj[MAX];

void maxFlow(int start, int end) {
    while (1) {
        fill(d, d + MAX, -1);
        queue<int> Q;

        Q.push(start);
        d[start] = 0;
        while (!Q.empty() && d[end]==-1) {
            int x = Q.front();
            Q.pop();

            for (int i = 0; i < adj[x].size(); i++) {
                int nx = adj[x][i];

                if (d[nx] == -1 && c[x][nx] - f[x][nx] > 0) {
                    d[nx] = x;
                    Q.push(nx);
                    if (nx == end) break;
                }
            }
        }

        if (d[end] == -1) {
            break;
        }
        int flow = INT_MAX;
        for (int i = end; i != start; i = d[i]) {
            flow = min(flow, c[d[i]][i] - f[d[i]][i]);
        }

        for (int i = end; i != start; i = d[i]) {
            f[d[i]][i] += flow;
            f[i][d[i]] -= flow;
        }

        res += flow;
    }
}

int CtoI(char c) {
    if (c <= 'Z') {
		return c - 'A';
    }
    else {
        return (c - 'a') + 26;
    }
}

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        char a, b;
        int q;
        cin >> a >> b >> q;

        int u = CtoI(a);
        int v = CtoI(b);
        c[u][v] += q;
        c[v][u] += q;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    maxFlow(0, 25);

    cout << res << '\n';

    return 0;
}