Untitled

mail@pastecode.io avatar
unknown
c_cpp
25 days ago
2.1 kB
4
Indexable
Never
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

using namespace std;


// variables

int c[702][702];
int flowpassed[702][702];
int parList[702];
int currentPathC[702];
vector<int> g[702];


// bfs

int bfs(int sNode, int eNode){

    memset(parList, -1, sizeof(parList));
    memset(currentPathC, 0, sizeof(currentPathC));

    queue<int> q;
    q.push(sNode);
    parList[sNode] = -1;
    currentPathC[sNode] = 999;

    while(!q.empty()){
        int currNode = q.front();
        q.pop();
        for(int i = 0; i< g[currNode].size(); i++){
            int to = g[currNode][i];

            if(parList[to] == -1){
                if(c[currNode][to] - flowpassed[currNode][to] > 0){
                    parList[to] = currNode;
                    currentPathC[to] = min(currentPathC[currNode], c[currNode][to] - flowpassed[currNode][to]);
                    if(to == eNode){
                        return currentPathC[eNode];
                    } // 0
                    q.push(to);
                } // 1
            } // 2
        } // 3
    } // 4
    return 0;
}
//

int edmondsKarp(int sNode, int eNode){
    int maxFlow = 0;
    while(true){
        int flow = bfs(sNode, eNode);//
        if(flow==0){
            break;
        }
        maxFlow += flow;
        int currNode = eNode; // sink에서 source로 역방향
        while(currNode!=sNode){
            int prevNode = parList[currNode];
            flowpassed[prevNode][currNode]+=flow; // 정방향
            flowpassed[currNode][prevNode]-=flow; // 역방향
            currNode = prevNode;
        }
    }
    return maxFlow;
}

int main(void){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    int n;
    cin >> n;
    char a,b;
    int value;
    for(int i = 0;i<n;i++){
        cin >> a >> b >> value;
        int aa = a - 'A';
        int bb = b - 'A';
        // cout << aa << " " << bb << '\n';
        c[aa][bb] = value;
        g[aa].push_back(bb);
        g[bb].push_back(aa);
    }

    int maxFlow = edmondsKarp(0, 25);
    cout << maxFlow << '\n';
}
Leave a Comment