6086 최대 유량

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

네트워크 플로우(Network Flow) 문제이다. 에드먼드-카프(Edmond-Karp) 알고리즘을 이용하여 A에서 Z까지의 최대 유량을 구한다. BFS로 증가 경로(Augmenting Path)를 찾아주면서 해당 경로상의 잔여 용량(Residual Capacity)의 최소값을 구한다. 그리고 유량의 대칭성을 유지하기 위해 유량을 보내는 방향의 간선들의 유량을 최소값만큼 늘리고 반대 방향의 간선들의 유량은 감소시킨다. 이 과정을 증가 경로를 더 이상 구하지 못할 때까지 반복하면 최대 유량을 구할 수 있다.

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 987654321
using namespace std;
 
int n,c[52][52],f[52][52];
 
void networkFlow()
{
    int totalFlow=0;
    while(true)
    {
        vector<int> p(52,-1);
        queue<int> q;
        p[0]=0,q.push(0);
        while(!q.empty() && p[25]==-1)
        {
            int now=q.front(); q.pop();
            for(int next=0;next<52;next++)
                if(c[now][next]-f[now][next]>0 && p[next]==-1)
                    p[next]=now,q.push(next);
        }
        if(p[25]==-1) break;
        int amount=INF;
        for(int i=25;i!=0;i=p[i])
            amount=min(c[p[i]][i]-f[p[i]][i],amount);
        for(int i=25;i!=0;i=p[i])
            f[p[i]][i]+=amount,f[i][p[i]]-=amount;
        totalFlow+=amount;
    }
    printf("%d\n",totalFlow);
}
 
int main()
{
    scanf("%d",&n);
    while(n--)
    {
        char a,b;
        int u,v,w;
        scanf(" %c %c %d",&a,&b,&w);
        if('A'<=a && a<='Z') u=a-'A';
        else u=a-'a'+26;
        if('A'<=b && b<='Z') v=b-'A';
        else v=b-'a'+26;
        c[u][v]+=w;
    }
    networkFlow();
    return 0;
}