17412 도시 왕복하기 1

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
vector<vector<int> > adj(405);
 
int cost[405][405] = { 0 };
int flow[405][405] = { 0 };
 
int main() {
    int n, p, rst = 0;
    scanf("%d %d", &n, &p);
 
    while (p--) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        cost[a][b] = 1;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    while (1) {
        queue<int> q;
        int visit[405] = { 0 };
        int prev[405] = { 0 };
 
        q.push(1);
        visit[1] = 1;
 
        int flag = 0;
        while (q.empty() == false) {
            int cur = q.front();
            q.pop();
            
            if (cur == 2) {
                flag = 1;
                break;
            }
            for (int i = 0; i < adj[cur].size(); i++) {
                int next = adj[cur][i];
 
                if (cost[cur][next] > flow[cur][next] && visit[next] == 0) {
                    visit[next] = 1;
                    prev[next] = cur;
                    q.push(next);
                }
            }
        }
        
        int end = 2;
        int cur = prev[end];
 
        if (flag == 0)
            break;
 
        int minFlow = cost[cur][end] - flow[cur][end];
        while (cur != 1) {
            cur = prev[cur];
            end = prev[end];
 
            minFlow = min(minFlow, cost[cur][end] - flow[cur][end]);
        }
        
        end = 2;
        cur = prev[end];
        flow[cur][end] += 1;
        flow[end][cur] -= 1;
        while (cur != 1) {
            end = prev[end];
            cur = prev[cur];
            flow[cur][end] += minFlow;
            flow[end][cur] -= minFlow;
        }
        rst += minFlow;
    }
    printf("%d", rst);
}

## 주의점

네트워크 블로우는 반드시, 

역방향 간선에 대해서 adj vector과 cost, flow 배열을 선언해서 계산해줘야 한다

minFlow도 반드시, cost - flow 식을 이용해서 구해야 한다

내 멋대로 하면 절대로 풀리지 않는다