3도 4도 모두 1,2를 먹을 수 있기 때문에, 누가 누굴 먹게 해주냐에는 관계없이 최대 유량 3이 흐릅니다.
3이 4를 먹게 해주는 경우, 3이 먹을 수 있는 상어의 집합은 (1,2,4), 4가 먹을 수 있는 상어의 집합은 (1,2)가 되고, 최대 유량은 3입니다. (3-1, 3-4, 4-2 또는 3-2, 3-4, 4-1)
반대의 경우, 3은 (1,2)를, 4는 (1,2,3)을 먹을 수 있게 되고, 최대 유량은 마찬가지로 3입니다. (3-1,4-2,4-3 또는 3-2,4-1,4-3)
최대 유량은 말 그대로 최대 유량으로, '잘못 흘러서 유량이 덜 흐르는 경우' 가 없게끔 할 수 있기 때문에 최대 유량 알고리즘이라 불립니다.
wlshddlek 5년 전
상어문제에서,, 이분매칭알고리즘으로 풀었는데,,능력치에 따라서 잡아먹을수있는 것들을 그래프에 넣은 후 dfs,이분매칭알고리즘을 돌리잖아요?
저렇게 코드짜면 맞긴하더라고요 그런데 생각해 보면 능력치가 같은경우,,,
if (power[i][0] == power[j][0] && power[i][1] == power[j][1] && power[i][2] == power[j][2])
{ graph[j].push_back(i); }
능력치가 같으면 i가 j를 먹어도되고 j가 i를 먹어도되므로 그냥 우리 맘대로 위 코드처럼 한쪽으로 정해버리잖아요? ,,근데 이렇게 우리가 정해놓으면 최선의 경우가 안나오는 경우가 생기지 않나요?
예를들어 1과 2는 서로 못잡아먹고 3은 1,2보다 능력치가 크고 3과 4의 능력치가 같을경우( 1!=2<3=4)
3이 4를 먹게해주는경우>>>>3이먹을 수 있는 거에 1,2,4를 다 넣어 주면 최대 2개밖에 못먹으니까 하나가 낭비되잖아요? 즉 총 2마리만 사라지는거죠(1,2)
4가 3을 먹게 해주는경우 >>>>이럴경우 차라리 4가 3을 먹게 해주면 3은 1,2를 먹고 4는 3을 먹으면 되므로 총 3마리가 사라질수 있잖아요
제가 뭘 잘못 생각하고있죠?