[일반] 오늘 엣코 G번이

[dd(211.109)]

https://www.acmicpc.net/problem/17506

Baekjoon Online Judge

이거랑 비슷한건가 maxflow로 조지려다가 털렸음...

[익명(211.57)]

나도 maxflow인가? 했는데 간선 2억 5천개 ㅋㅋㅋㅋ

[익명(211.57)]

근데 maxflow가 맞네 ㅁㅊ 민컷으로 역으로 플로우 구해버리네 ㄷㄷ

[dd(211.109)]

공식 에디토리얼은 dp던데... 흠 어렵군요

[대학원오지마세요(publfl)]

maxflow를 mincut으로 보고 어떤 edge를 처음에 자를지 보면 imos법 같은 형태가 나옵니다. 어떤 edge자르는지 결정은 DP로 N^2에 보면 되고, 그 후는 imos써서 mincut 계산하면 됩니다

[대학원오지마세요(publfl)]

옛날 ARC-E에 maxflow를 mincut으로 계산하는 문제가 정확히 똑같이 나온적 있어서 이 테크닉은 웰노운이라 생각해요

[dd(211.109)]

maxflow를 압축해서 하는 느낌인건가요...? 감이 안잡히네요 성님

[대학원오지마세요(publfl)]

왼쪽에 공번호들을 모아놓고, 오른쪽에 박스번호 모아놓으면 여기서 대충 간선 잘만들어서 maxflow 흘려주면 답이 되는건 명확히 보입니다. 다만 maxflow 알고리즘을 그대로 쓰면 시간,공간 다 터지기 때문에 mincut으로 바꾸는 테크닉을 써야해요. 그러면 mincut은 어떻게 계산해주냐인데, source -> 공번호 로 가는 edge들을 원하는 만큼 잘랐다고 합시다. 그리고, source->공번호로 가는 edge가 남아있는(즉, 잘리지 않은) 공번호의 집합을 S라고 해줍시다. 그러면, 오른쪽 노드들을 봤을때, S->v로 가는 edge 집합이 있고, v->sink로 가는 edge가 있습니다. 둘중 하나는 무조건 끊어야해요. 그래야 cut이 되기 때문에

[대학원오지마세요(publfl)]

S->v로 가는 edge집합의 cost는 S에 속한 node번호 합 x v가 되고, v->sink로 가는 edge의 cost는 B_v가 됩니다. 그래서 v마다 잘리는 cost는 min( S x v , B_v)가 되서, cut의 value = source-> S에 속하지 않는 node로 가는 edge 끊는데 드는 최소비용 + sum_v min(S x v + B_v)가 됩니다. sum_v min(S x v + B_v)는 S에 속한 node들의 번호합을 가지고 생각해보면 imos로 계산할 수 있고, source-> S에 속하지 않는 node로 가는 edge 끊는데 드는 최소비용은 O(N^2) DP로 해결 가능합니다.

[dd(211.109)]

아니 뭔 이런 발상은 어떻게 하는건지....

[dd(211.109)]

무슨말인지 이해했는데 진짜 이걸 대회중에 떠오르는 게... 어렵네요 감사합니다!