oVeron

집에서 학교까지 가는 최소 컷을 구하는 문제이다. 여기서는 디닉 알고리즘을 사용했지만 에드몬드-카프로도 해결할 수 있다. 기준이 간선이 아닌 정점이기 때문에, '2316번: 도시 왕복하기 2'와 같이 정점을 간선으로 만드는 테크닉이 필요하다.#include using namespace std;typedef long long ll;typedef pair pii;typedef pair pll;typedef tuple tiii;const int MAXN = 200;const int INF = 1e9;int N, M;char board[MAXN][MAXN];map cap, fl;int S, T;int dist[MAXN*MAXN];int dir[2][4] = {{-1, 1, 0, 0}, {0, 0, -1, 1}}..

알고리즘/baekjoon 2024. 7. 4. 12:49