MCMF 썸네일형 리스트형 BOJ)3640 제독 문제: icpc.me/3640 경로가 겹치지 않게 두가지 방법으로 목적지 까지 갈 때 사용되는 최소 비용을 구하는 문제이다. 경로가 겹치지 않는 두가지 방법을 구하는 모델링은 네트워크 플로우 이론에서 정점 분할을 한 뒤 간선과 정점 사이의 모든 capacity를 1으로 준 뒤 플로우를 흘려주는 것으로 가능하다. 이 때 두가지 방법으로 이동할 때 드는 최소 비용을 구하는 문제이므로 MCMF를 이용하여 minimum cost를 구하되 sink까지 플로우를 두번만 흘려주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697.. 더보기 BOJ)11409 열혈강호 6 문제: icpc.me/11409 Maximum Cost Maximum Flow를 구하는 문제이다. 기존 MCMF 모델링에서 cost만 음수값으로 취해준 뒤 계산해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include #include #include #include #define INF 987654321using namespace std;struct Edge { int v, cost, cap, rev; Edge(int v, int cost.. 더보기 BOJ)11408 열혈강호5 문제: icpc.me/11408 직원들이 일을 할 수 있을 만큼 최대한 시킬 때 지급해야 하는 월급의 최솟값을 같이 구해주는 문제이다. 문제에서 요구하는 조건은 MCMF로 구해줄 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788#include #include #include #include #define INF 987654321using namespace std;struct Edge { int v, cost, cap, rev; Edge(int v,.. 더보기 이전 1 2 다음