17412번: 도시 왕복하기 1 - 네트워크 유량

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

const int MAXN = 401;
const int INF = 1e9;
struct node
{
    int next; //다음 노드
    int cap, fl; //용량, 유량
};
int N, P;
vector<node> graph[MAXN];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	cin >> N >> P;
	while(P--) 
	{
	    int u, v; cin >> u >> v;
	    graph[u].push_back({v, 1, 0});
	    graph[v].push_back({u, 0, 0});
	}
	
	int ans = 0;
	int source = 1, sink = 2;
	while(true)
	{
	    int par[MAXN];
	    int nxIdx[MAXN], prIdx[MAXN];
	    //nxIdx[u] : 벡터 graph[par[u]]에서 next가 u인 index
	    //prIdx[u] : 벡터 graph[u]에서 next가 par[u]인 index
	    memset(par, -1, sizeof(par));
	    par[source] = source;
	    
	    queue<int> qu;
	    qu.push(source);
	    
	    while(!qu.empty() && par[sink] == -1) //BFS
	    {
	        int u = qu.front(); qu.pop();
	        for(int i=0; i<graph[u].size(); i++)
	        {
	            node city = graph[u][i];
	            if(city.cap - city.fl > 0 && par[city.next] == -1) //유량이 0 이상이고, 부모가 없어야 한다.
	            {
	                qu.push(city.next);
	                par[city.next] = u;
	                nxIdx[city.next] = i;
	            }
	            if(city.next == par[u]) prIdx[u] = i;
	        }
	    }

	    if(par[sink] == -1) break;
	    
	    int FL = INF;
	    for(int u = sink; u != source; u = par[u]) //흘릴 수 있는 유량 구하기
	    {
	        node city = graph[par[u]][nxIdx[u]];
	        FL = min(FL, city.cap - city.fl);
	    }
	    for(int u = sink; u != source; u = par[u]) //유량 업데이트
	    {
	        node& nxCity = graph[par[u]][nxIdx[u]];
	        node& prCity = graph[u][prIdx[u]];
	        nxCity.fl += FL;
	        prCity.fl -= FL;
	    }
	    
	    ans++;
	}
	cout << ans;
}