백준[6086] 최대 유량

문제 설명

문제 링크

http://icpc.me/6086

6086번: 최대 유량

풀이

네트워크 플로우로 풀 수 있다.

여기를 참고했다.

코드

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct Edge {
    int to, c, f;
    Edge *rev;
    Edge(int a, int b) : to(a), c(b), f(0), rev(nullptr) {}
    int spare() { return c - f; }
    void addFlow(int ff) {
        f += ff;
        rev -> f -= ff;
    }
};

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

const int V = 66;
const int INF = 1e9;
vector<Edge*> v[V];

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        char a, b; int c; 
        scanf(" %c %c %d", &a, &b, &c);
        a = ctoi(a); b = ctoi(b);
        Edge *e1 = new Edge(b, c), *e2 = new Edge(a, c);
        e1 -> rev = e2;
        e2 -> rev = e1;
        v[a].push_back(e1);
        v[b].push_back(e2);
    }

    int total = 0, S = ctoi('A'), E = ctoi('Z');
    while (1) {
        int prv[V];
        Edge *path[V] = {0};
        fill(prv, prv + V, -1);
        queue<int> q;
        q.push(S);
        while (!q.empty() && prv[E] == -1) {
            int cur = q.front();
            q.pop();
            for (auto e : v[cur]) {
                int nxt = e -> to;
                if (e -> spare() > 0 && prv[nxt] == -1) {
                    q.push(nxt);
                    prv[nxt] = cur;
                    path[nxt] = e;
                    if (nxt == E) break;
                }
            }
        }
        if (prv[E] == -1) break;

        int flow = INF;
        for (int i = E; i != S; i = prv[i]) flow = min(flow, path[i] -> spare());
        for (int i = E; i != S; i = prv[i]) path[i] -> addFlow(flow);
        total += flow;
    } 
    printf("%d", total);
}