Need simple advice for graph solving problem
- by sap
Hi there,
a collegue of mine proposed to me an exercise from an online judge website, which is basically a graph solving problem of an evacuation plan on a small town.
i dont need the answer (nor do i want it) i just need an advice on which is the best approach to solving it since im kinda new to these kind of problems.
the problem consists of town buildings with workers and fallout shelters in case of a nuclear attack. i have to build an algorithm that will assign the workers of each building to one or more fallout shelters but in a way that some shelters wont became too overcrowded while others remain almost empty (else i would just make the workers go to the nearest one).
the problem is this: http://acm.timus.ru/problem.aspx?space=1&num=1237
in case its offline heres the google cached version of it: http://webcache.googleusercontent.com/search?q=cache:t2EPCzezs7AJ:acm.timus.ru/problem.aspx%3Fspace%3D1%26num%3D1237+vladimir+kotov+evacuation+problem&cd=1&hl=pt-PT&ct=clnk&gl=pt
what i've done so far is for each building get the nearest shelter and move the number of workers from that build equal to the shelter capacity. then move to the next building. but sometimes the number of workers is greater than the shelter capacity, in that case after i iterate through every building, ill just iterate then again apllying the same algorithm until every building has 0 workers in it, problem is this is hardly the best way to solve it.
any tip is welcome, please dont feel like im asking for the answer, i just want an advice in the right direction of solving it.
thanks in advance.
