wwiiiii   7년 전

4716번 풍선 문제입니다.

각 팀을 노드로 생각하고, 소스/방 A/방 B/싱크 노드를 따로 만든 뒤 [소스 -> (방 A/방 B) -> 각 팀 -> 싱크] 꼴로 엣지를 연결시켜 그래프를 구축했습니다. 그 다음에 MCMF를 구할 때는 벨만 포드로 현재 가능한 소스->싱크 경로 중 비용이 최소가 되는 것을 찾고, 그런 경로가 있으면 결과값을 그만큼 갱신하다 그런 경로가 없으면 결과값을 반환하게 짰습니다. 음수 사이클이 생기진 않을 것 같은데 어디서 TLE가 나는 걸까요?

dotorya   7년 전

이 문제의 경우는 유량이 최대 10000, 플로우 그래프의 정점, 간선이 1000개 정도씩이니, 최악의 경우 10000 * (1000*1000) 정도의 시간이 들 수 있습니다. 플로우 특성상 이것보다 좀 적게 들긴 하겠지만, 여전히 TLE가 날 가능성은 있을 것 같네요.

이 문제는 MCMF를 사용하는 것보다 더 좋은 알고리즘이 있습니다. 다른 방법을 찾아보시면 좋을 것 같습니다!

wwiiiii   7년 전

감사합니다! 확실히 더 쉬운 방법이 있긴 하네요 MCMF 연습해보고 싶어서 분류 중 맨 위 문제 골랐던 건데 ㅠㅠ

sgc109   7년 전

@wwiiiii 저도 mcmf 연습할려고 맨위 문제골라서 증가경로는 SPFA으로 MCMF 구현해서 제출했는데 TLE 떴네요.. 분류가 MCMF 라 이렇게 푸는게 정해인줄알았는데 역시 최악의 경우 시간이 많이 들긴하나보네요..ㅠㅠ 혹시 더 쉬운 방법이 뭔지 알 수 있을까요??

wwiiiii   7년 전

@sgc109 그냥 이렇게 쓰면 되는건가? 저는 일종의 그리디로 풀었어요 일단 할당 가능하게 다 배정한 다음에 각각에서 정렬 상태 유지하고 바꿔서 이득이면 계속 바꾸는 식으로 했어요

sgc109   7년 전

@wwiiiii 그렇군요 저도 그리디로 한번 작성해봤는데 틀렸습니다 가 뜨는데 혹시 어디가 문제인지 봐주실수있나요? 

저도 A,B 중에 작은 비용을 갖는 쪽으로 우선 다 보내서 총 비용을 계산해놓은뒤 

A와 B의 비용차와 팀의인덱스를 pair 로 만들어서 정렬한뒤 비용차가 가장적은것부터 순회하며 구역(AorB)의 풍선개수를 초과하는 쪽을 같거나 작아질때까지

비용차가 적은것순으로 차례로 반대 구역으로 보내주면서 차이나는 비용만큼 총 비용에 더해주는식으로했고

만약 비용차가 적지만 애초에 A와 B중 더 비용이 적은 쪽이 풍선 개수가 남는 쪽이라면 continue 를 하여 그대로 유지시켜주었습니다.


아래 소스에서 

n은 팀의개수

want 는 각 팀에 필요한 풍선의 개수

cntA,B 는 A,B구역 각각에 있는 풍선의 개수

flowA,B 는 팀들이 A,B구역에서 풍선을 가져갈 총 개수

cost 는 각팀별로 A,B 구역까지의 거리

diffs 는 A와 B구역까지 각각의 거리의 차가 적은순으로 정렬하기위한 벡터

입니다.

wwiiiii   7년 전

@sgc109 일단 이건 제 소스인데 알고리즘은 같아요. 아마도 구현 부분에서 문제가 있는 듯 한데 찾아볼게요

wwiiiii   7년 전

@sgc109

72~76번째 줄에서 flowA-cntA만큼 A에 속해있던 것을 B로 넘겨주는거 같은데
flowA-cntA만큼 B로 넘겨줬을 때 원래 flowB <= cntB였는데 넘겨준 후
flowB > cntB가 되는 경우 이번에 넘겨준 풍선의 소속이 B로 표시?가 안돼 있어서
다음부터 고려가 안될 것 같고 flowA-cntA값도 따로 저장을 안하고 그대로 쓰셔서
totalCost += diffs[pos].first*(flowA-cntA);
flowA-=flowA-cntA; // 여기서 flowA-cntA의 값이 바뀝니다.
flowB+=flowA-cntA;

sgc109   7년 전

@wwiiiii 댓글감사합니다! 제가 지적해주신부분을 봤는데 

문제에서 주어진 조건(A와 B에 있는 풍선의 합은 각팀이 필요로하는 풍선의 개수의 합보다 크거나 같다)때문에

처음에 flowB <= cntB  이다가 flowA-cntA 를 더했을때 flowB > cntB 가 되는 경우는 없지않나요?

왜냐하면 flowA-cntA를 flowA에서 빼줬다는건 flowA를 딱 cntA로 맞춰줬다는건데 그걸 flowB에 더해서 flowB가 cntB보다 커졌다면 애초에 풍선이 부족하다는 뜻이니까요.

그리고 두번째로 지적해주신 중간에 flowA의 값이 의도치않게 바뀌어 버리는것에대해선 확실히 제가 간과한부분이네요.. 그런데 저는 마지막에 cntA(orB)보다 컸던 쪽의 flowA(orB)의 값을 cntA(orB)에 맞추는 순간 가장 바깥에 있는 반복문을 벗어날 것이고 그렇게되면 필요한것은 totalCost 뿐이라고 생각해서 큰 차이는 없을 것이라고 생각했는데 그 부분을 수정하니까 바로 틀렸습니다. 에서 16%까지 맞고 틀렸습니다. 로 바뀌었네요..

혹시 제가 생각한것에 틀린게 있나요??

wwiiiii   7년 전

@sgc109 생각한 것은 전부 다 맞고요, 되게 사소한 거에서 에러가 났네요. A까지의 거리와 B까지의 거리가 둘다 같으면 A팀에 먼저 배정하게 되었는데 79번째 줄에서 보면 B에 배정된게 제한값보다 클 때 B에 할당된 것을 A에 넘겨주잖아요? 그 때 distA < distB면 A에 배정되어 있을거니까 continue하게 했는데 둘이 같은 경우도 A에 배정되어 있을 것이므로 continue 시켜야합니다. 즉 79번째 줄의 조건문을 if(cost[diffs[pos].second][1] >= cost[diffs[pos].second][0])로 고치면 맞게 고쳐지네요!

sgc109   7년 전

@wwiiiii 아...같을때 제대로 차리를 안해줬네요.. 감사합니다~!

댓글을 작성하려면 로그인해야 합니다.