구사과

https://www.acmicpc.net/problem/3419격자 그래프가 주어질 때, 갔던 정점을 다시 들리지 않는 조건으로 First와 Second가 번갈아 움직인다. 움직일 수 없는 사람이 질 때, 각각의 정점을 시작점으로 했을 때, 각각의 정점에서 누가 이기는지를 출력하면 된다.격자 그래프는 이분 그래프다. 정점을 두 집합으로 쪼개서, 현재 정점이 속한 집합을 A, 반대 집합을 B라고 하자. 이 문제의 답은 이분 그래프의 최대 매칭과 관련이 있다.설명을 돕기 위해, 먼저 매칭 크기 == |A| 인 경우를 생각해 보자. 이 때는 First가 A에서 매칭된 B의 정점으로만 움직여주면, 항상 이길 수 있다. B가 어떻게 움직이든간에, A 집합에 있는 정점으로 다시 가게 될 것이고, 그 정점은 매칭에..

(Single, 1985) 유투브 연관 동영상으로 엮여서 들었는데.. 하이라이트 부분의 마성의(?) 신디 소리에 빠져서 무한반복 중이다. 취향저격..

ASC 1. Reactor Coolinghttp://codeforces.com/problemset/gymProblem/100199/B 아무 circulation이나 찾으면 되고, 일반적으로 이것은 그냥 아무것도 흘려주지 않으면서 (...) 해결할 수 있다.하지만 에지의 flow 량이 Fi, j  이를 해결하기 위해서는, 양변에 Li, j를 빼줘서 Fi, j 당연히 단순히 이것으로 되지는 않는데, 양변에 빼줬으니, 정점 j는 그 대신 Li, j만큼의 유량을 보장받아야 하고, 정점 i 역시 Li, j만큼의 유량을 흘려야만 한다.고로, source와 sink를 만들어줘서, 이 정점에서 그 유량을 흘려주면 된다. max flow의 합이 Sum(Li, j)가 된다면, 모든 유량이 보장받았고, 해가 존재한다.cpp..