상당히 재밌게 풀은 문제이다. 이 문제를 풀기위해서는 여러 도로들을 거치면서 사람이 지나갈 수 있는 정도를 이해해야한다. 예를 들어 1번에서 2번으로 가기 위한 간선은 매 단위시간마다 2명이 들어설 수 있고 지나가려면 단위 시간 3이 필요하고 2번에서 3번으로 가기 위한 간선은 매 단위시간마다 1명이 들어설 수 있고 지나가려면 단위 시간 5가 필요하다고 하자. 그러면 1번에서 3번으로 가기 위해서는 간선 (1,2)와 (2,3)을 거쳐가야하는데 이 과정에서 두번째 간선의 유입량이 1로써 제일 작으므로 사실상 단위 시간당 3번으로 빠져나오는 양은 1이다. 즉, 빠져나오는 양은 간선의 단위 시간 당 들어올 수 있는 사람의 수의 최솟값이다. 사람의 유입되고 그것을 산출하는 방식이므로 Network flow로 이..

백준 2316번 도시 왕복하기 2 문제와 매우 유사하다.(viyoung.tistory.com/160) 이 문제를 보고 최소 컷 문제라는 것을 인식할 수 있다. 다만, 일반적인 최소것 문제의 경우에는 간선을 자르는데 이 문제는 정점을 잘라야 한다. 즉, 정점에 capacity를 줘서 처리하는 정점 분할 기법을 사용한 뒤 최소 컷을 구해주면 된다. 또한 Max flow Min cut Theorem에 의하여 이 문제는 다시 최대 유량 문제로 돌려서 구해주면 된다. 다만, 정점 분할을 진행할 경우에 주의해야할 지점은 source와 sink를 처리함에 있어서 매우 주의해야 한다. (53번째 줄에서 예외처리해준 사항에 대해서 매우 주의하도록 하자.) #include #define fastio ios_base::sy..

기본적으로 백준 7616번과 완전하게 동일하다. (viyoung.tistory.com/159) 2번이상 방문하지 않는다는 상황을 정점 분할해서 처리해주면 된다. 정점 분할하는 방법은 해당 index에 2배 처리해줘서 찢어주면 된다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define INF 123456789; const int MAX_N = 802; using namespace std; struct edge{ int from, to, capacity, flow; edge* reverse_edge; edge(int u, int v, int c) : from(u), to(v), capacity(c), fl..

이 문제에서 가장 중요한 지점은 경로도 겹치지 말아야하지만 노드도 겹치면 안된다는 점이다. 경로가 겹치지 않는 것은 최대유량으로 충분히 처리할 수 있다. 그런데 노드가 겹치지 말아야한다는 것은 일종의 노드에 capacity를 주는 느낌으로 이해할 수 있다. 이를 해결하기 위해서는 정점을 in과 out을 구분하는 "정점 분할"을 활용하면 된다. 서로 다른 노드끼리 연결하는 경우에는 반드시 out -> in으로만 가능하고 내부 정점에서는 in -> out로만 이동하게 하고 in -> out에 capacity를 1을 줌으로써 해결할 수 있다. 대략적으로 이런방식으로 처리를 해주면 된다. 그러면 한 노드 안에서도 capacity가 생성되어 1번만 방문하게끔 유도할 수 있다. 다만, 유의해야할 점은 flow를 줘..