1049 - Remember the A La Mode!

All about problems in Volume 10. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

1049 - Remember the A La Mode!

Post by Riyad »

http://acmicpc-live-archive.uva.es/nuevoportal/

i think the problem is about weighted bipartite matching . so hungarian method or min cost max flow is the way to go . but considering generally the number of vertices is huge , so its gonna time out . so how to build the flow network ? is it possible to solve this problem without modifying the above mentioned algorithms ?? any trick im missing .....could any one please help me ........
bye bye
Riyad
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh »

Why is the number of vertices too large?

If you use hungarian, maybe, because you might have to expand each vertex into many vertices.

But not if you use min-cost max-flow.

My team in the 2006 world finals got accepted with a direct min-cost max-flow implementation.

User avatar
Riyad
Experienced poster
Posts: 131
Joined: Thu Aug 14, 2003 10:23 pm
Location: BUET
Contact:

Post by Riyad »

could you please explain the idea to solve the problem a little clearly . how come by min cost max flow u dont have to expand the nodes of each category ...................
Please Help
HOLD ME NOW ,, I AM 6 FEET FROM THE EDGE AND I AM THINKIN.. MAY BE SIX FEET IS SO FAR DOWN

chrismoh
New poster
Posts: 35
Joined: Mon Dec 10, 2001 2:00 am
Location: Singapore; Cambridge, MA

Post by chrismoh »

Well, a simple min/max cost max flow formulation is this:

Have a super-source s.

From s to every pie have an edge with cost 0 and capacity the number of pies.

Have a super-sink t.

From every ice-cream to t have an edge with cost 0 and capacity the number of ice-creams.

For every (pie, ice-cream) combo that works, have an edge from the pie to the ice cream with cost the given cost and infinite capacity.

A max-flow min-cost will give the minimum profit, and a max-flow max-cost will give the maximum profit.

Post Reply

Return to “Volume 10 (1000-1099)”