상당히 재밌게 풀은 문제이다. 이 문제를 풀기위해서는 여러 도로들을 거치면서 사람이 지나갈 수 있는 정도를 이해해야한다. 예를 들어 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..

최소 컷을 묻는 것이므로 Max Flow min Cut 정리에 의해서 사실상 이 문제는 최대 유량을 물어보는 것과 동치이다. 다만, 이 문제에서 가장 중요한 지점은 무방향 그래프라는 것이다. (이 부분 때문에 한번 미스났다..ㅋㅋ) #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define INF 987654321; const int MAX_N = 501; 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..

느낌이 열형강호 2랑 되게 유사하다. 그런데, 이 문제의 경우는 여러개 선택하는 경우가 없기떄문에 단순하게 이분매칭으로 풀어도 무방하다. 가상의 source와 sink를 잡고 모든 간선들의 capacity를 1로 설정해주면 네트워크 모델링해서 이 문제를 쉽게 해결할 수 있다. #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); using namespace std; const int MAX_N = 402; struct edge{ int from, to, capacity, flow; edge* reverse_edge; edge(int u, int v, int c) : from(u), to(v), capacity(c), ..

백준 2316번을 풀고 푸니 되게 쉬웠다 경로는 한번만 갈 수 있으므로 방향 그래프의 capacity를 1로 주고 max_flow를 구하면 된다. 매우 쉽다 #include #define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); #define INF 987654321; const int MAX_N = 401; using namespace std; typedef pair pii; struct edge{ int from, to, flow, capacity; edge* reverse_edge; edge(int u, int v, int c) : from(u), to(v), capacity(c), flow(0) {} int residual(){..

잘 생각해보면 애드몬드 카프 기법에서 capacity의 최솟값을 잡고 이를 기준으로 flow를 결정하게 된다. 즉, 최대유량을 결정하는 인자는 적어도 residual이 0일수밖에 없다. 다만, 유의해야할 지점은 해당 내용이 완전 중요한 간선의 필요조건이지 충분조건은 아니라는 점이다. 예를 들어 1 -> 2로 가는 간선의 residual이 포화되었다고 가정하자 이떄, 1 -> 3 -> 2의 mnimum residual이 0보다 클 경우에는 1 -> 2로 가는 유량의 일부를 다른 노선으로 흘려줄 수 있다. 즉 필수불가결한 노선은 아닌 것이다. 이러한 방식으로 완전 중요한 간선을 확보해주면 된다. 구하는 방법은 생각보다 되게 단순한데, 이미 기존에 adj배열이 있고 networkFlow 함수를 활용해서 해당 ..

기본적으로 백준 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를 줘..