Edmonds-Karp

설명은 추후 업로드

// Algorithm Analysis
// 네트워크 플로우 (Network Flow)

#include <iostream>
#include <vector>
#include <queue>

#define MAX 100
#define INF 1000000000

using namespace std;

int n = 6;
int result;
int cap[MAX][MAX]; // 용량
int flow[MAX][MAX]; // 현재 사람의 수
int vtd[MAX]; // 현재 장소 방문 여부

vector<int> a[MAX];

// 최대 사람의 수 계산
void maxFlow(int s, int e) {
	while (1) {
		fill(vtd, vtd + MAX, -1);
		queue<int> q;
		q.push(s);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			for (int i = 0; i < a[x].size(); i++) {
				int j = a[x][i]; // 인접 정점 가져옴
				// 방문하지 않은 정점 중 용량이 남은 경우
				if (cap[x][j] - flow[x][j] > 0 && vtd[j] == -1) { // 흐를 수 있는 경우 && 방문하지 않은 경우
					q.push(j);
					vtd[j] = x; // 경로를 기억함
					if (j == e) break; // 도착지에 도달한 경우
				}
			}
		}
		// 모든 경로를 다 찾은 경우
		if (vtd[e] == -1) break;
		int f = INF;
		// 거꾸로 최소 사람 수 탐색
		for (int i = e; i != s; i = vtd[i]) {
			f = min(f, cap[vtd[i]][i] - flow[vtd[i]][i]);
		}
		// 최소 사람 수만큼 추가
		for (int i = e; i != s; i = vtd[i]) {
			flow[vtd[i]][i] += f;
			flow[i][vtd[i]] -= f;
		}
		result += f;
	}
}

int main() {
    int n, m; // 장소의 수, 에스컬레이터의 수
    int p, q; // 출발점, 도착점
    cin >> n >> m;
    cin >> p >> q;
    for(int i=0; i<m; i++){
        int s, t, u; // 시작 장소의 번호, 에스컬레이터 한 번을 통한 도착 장소의 번호, 해당 에스컬레이터가 수용 가능한 사람의 수
        cin >> s >> t >> u;
        a[s].push_back(t);
        a[t].push_back(s);
        cap[s][t]=u;
    }

	maxFlow(p, q);
	printf("최대 탑승 가능한 사람의 수 : %d", result);
}