PAT T1003 Universal Travel Sites

#include<bits/stdc++.h>

using namespace std;

const int maxn=;

const int inf=1e9;

queue<int> q;

int M,N;

int g[maxn][maxn];

int pre[maxn];

int flow[maxn];

int maxflow;

unordered_map<string,int> pos;

int bfs (int s,int t) {

    while (!q.empty()) q.pop();

    for (int i=;i<=N;i++) pre[i]=-;

    pre[s]=;

    q.push(s);

    flow[s]=inf;

    while (!q.empty()) {

        int x=q.front();

        q.pop();

        if (x==t) break;

        for (int i=;i<=N;i++) {

            if (g[x][i]>&&pre[i]==-) {

                pre[i]=x;

                flow[i]=min(flow[x],g[x][i]);

                q.push(i);

            }

        }

    }

    if (pre[t]==-) return -;

    else return flow[t];

}

void Edmonds_Karp (int s,int t) {

    int increase=;

    while ((increase=bfs(s,t))!=-) {

        int k=t;

        while (k!=s) {

            int last=pre[k];

            g[last][k]-=increase;

            g[k][last]+=increase;

            k=last;

        }

        maxflow+=increase;

    }

}

int main () {

    string s1,s2;

    cin>>s1>>s2>>M;

    pos[s1]=;

    pos[s2]=;

    int cnt=,x;

    for (int i=;i<M;i++) {

        cin>>s1>>s2>>x;

        if (pos[s1]==) pos[s1]=cnt++;

        if (pos[s2]==) pos[s2]=cnt++;

        g[pos[s1]][pos[s2]]=x;

    }

    N=cnt-;

    Edmonds_Karp (,);

    printf ("%d",maxflow);

    return ;

}