OJ Board

Hi, this is my approach to the problem:

- Apply Dijkstra for each of the possible subsets of people into a car.
- Then i have to find disjoint-subsets (which represent people in the cars) whose union has all the people and their sum of costs (obtained by Dijkstra) is minimal.

For the second part i ...

That was exactly the explanation i was looking for, thanks.

Hi, i wish to know how to solve the problem of finding a maximal matching with minimum weight in general graphs, (not just bipartite graphs), from comments about problem 10911, it seems to be an algorithm in O(2^n * n^2), wich uses DP, i am particularly interested in this solution, because i have ...

yes, that was 10989, it was exactly the same as the 900 in SRM 334, although one could pass the TC one with a less efficient algorithm.

As Darko mentions, it was relativately common see UVA problems on TC, but i had never seen a TC problem on UVA

is this the beginning of a war UVA vs TC?

Actually, 11157 is (almost) the same as a past regional contest (SWERC 01) problem:


http://acmicpc-live-archive.uva.es/nuev ... php?p=2425


so, this should have been called, the "pirat" contest

Any hint or idea about solving problem B without computing Voronoi diagram?

Two buildings are neighbor if their minimum distance be less than 30 (meters).

How to determine this mnimum distance between the polygons?

Maybe this input is useful for those geting WA:


2
0 (1) 1
1 (1) 0

20
0 (1) 1
1 (4) 0 2 4 5
2 (4) 1 5 6 10
3 (1) 4
4 (4) 1 3 5 8
5 (6) 1 2 4 8 9 10
6 (3) 2 10 13
7 (1) 8
8 (4) 4 5 7 9
9 (3) 5 8 10
10 (4) 2 5 9 6
11 (3) 12 13 17
12 (3) 11 14 15
13 (5) 6 11 14 17 18
14 (4) 12 13 15 18
15 (4) 12 14 ...

After i have read what vertex cover problem is, i agree this problem asks for the vertex cover, but how can you compute it?, specially when this is a NP problem whit n=30, do you have to make some kind of backtracking with pruning or something like that?, thanks in advance

it seems right, Japan would be great

Thanks for your help, now i think i understand the problem well, and solved several problems too , thanks again

ok, thanks for replying, i think i have understood now, and i think i have implemented right, i just have some doubts, maybe you can answer me:

(1) why the potential assigned to each vertex grantes us that there is no negative path?

(2) i dont understand how can i modify this algorithm to allow ...

hi, in the past days i have read somewhat about the mincost maxflow algorithm, and i have realized this seems to be an "obscure" topic, because although there is information about the algorithms, little is covered about an actual implementation in a language like c++, this has been what i have ...

What's the approach or mathematical concept required to solve this problem?

I used map<int,int> for this problem and get AC in 0.6 sec , i keep record of the time i was on a particular number, so when i found a number which was inserted in the map i found a cycle, so the length of the cycle is current_time - time_recorded_in_map