Any hints how to do this.... I tried to think of possible greedy algs, but each one seemed to have a snag...
Thanks....
Problem 3277 : Workshops
Moderator: Board moderators
Do you mean weighted bipartite matching?Moha wrote:We solved it in contest by Graph matching.
I've been attempting to implement this using Ford-Fulkerson and a modified Dijkstra (to avoid the problem of negative weighted edges). However, it is too slow: O(v^3) where v=1000.
Could you give details about how you solved it?
I thought I could find a counter-example to your greedy choice, but I can't seem to find it at this moment.
Practicing for the world finals I wrote a greedy solution, and I ended up proving to myself that it cannot possibly be greedy (any choice of picking has a counter example). Maybe I didn't think about this choice... I'll go change my ordering to this and see if it works on my test set.
Nate
Practicing for the world finals I wrote a greedy solution, and I ended up proving to myself that it cannot possibly be greedy (any choice of picking has a counter example). Maybe I didn't think about this choice... I'll go change my ordering to this and see if it works on my test set.
Nate
Re: Problem 3277 : Workshops
edit: can two workshop share the same room at the same time if the room has sufficient capacity