Thursday, August 14, 2014

National Olympiad in Informatics, China, 2006 Day 2, Problem 1 - Maximum Profit

Problem Link

정점 n개와 간선 m개가 있는데, 정점에는 음의 가중치가 있고, 간선에는 양의 가중치가 있다. 이 때 정점을 몇 개 고르면, 그 정점들로 구성되는 간선을 모두 선택할 수 있다. 정점을 잘 골라서 정점들과 간선들의 가중치의 합을 최대화하는 문제이다.
MCMF인 것 같지만, Min-Cut 문제이다. 이분 그래프 구성법이 독특하여 매우 어려운 문제였는데, 왼쪽에는 간선들을, 오른쪽에는 정점들을 두고
1) 소스에서 간선들에는 유량을 간선의 가중치만큼 준다.
2) 간선에서(u-v면 i->u, i->v) 정점들에는 유량을 무한대 준다.
3) 정점에서 싱크에는 유량을 정점의 가중치만큼 준다.
위 처럼 이분 그래프를 구성하고 max-flow 돌린 다음에, 간선들의 가중치 합에서 maxflow값을 빼주면 됨. 가중치의 합을 최대화하는 문제를, 전체 가중칭서 빼주는 가중치의 합을 최소화하는 문제로 바꿔서 생각해보는 것이 중요하다고 할 수 있겠다.

Source Code

No comments:

Post a Comment