## Search found 21 matches

Tue Sep 25, 2007 3:01 am
Forum: Volume 112 (11200-11299)
Topic: 11288 - Carpool
Replies: 1
Views: 1258

### 11288 - Carpool

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 d...
Mon Jan 22, 2007 9:00 pm
Forum: Algorithms
Topic: General Weighted Perfect Matching
Replies: 2
Views: 1772
That was exactly the explanation i was looking for, thanks.
Fri Jan 19, 2007 3:07 am
Forum: Algorithms
Topic: General Weighted Perfect Matching
Replies: 2
Views: 1772

### General Weighted Perfect Matching

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 no...
Mon Jan 15, 2007 8:24 pm
Forum: Bugs and suggestions
Replies: 11
Views: 3362
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?
Mon Jan 15, 2007 6:42 pm
Forum: Bugs and suggestions
Replies: 11
Views: 3362
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
Tue Dec 12, 2006 11:15 pm
Forum: Algorithms
Topic: Problem J - World Finals 2005
Replies: 11
Views: 6689
Any hint or idea about solving problem B without computing Voronoi diagram?
Sat Oct 28, 2006 2:43 am
Forum: Volume 111 (11100-11199)
Topic: 11144 - S.O.S.
Replies: 13
Views: 4903

Two buildings are neighbor if their minimum distance be less than 30 (meters).
How to determine this mnimum distance between the polygons?
Fri Sep 29, 2006 2:31 am
Forum: Volume 7 (700-799)
Replies: 54
Views: 22249
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 16 1...
Sun Sep 24, 2006 2:15 am
Forum: Volume 110 (11000-11099)
Topic: 11095 - Tabriz City
Replies: 14
Views: 6047
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
Wed Sep 13, 2006 8:02 pm
Forum: Other words
Topic: 2007 world finals IN JAPAN?
Replies: 20
Views: 10483
it seems right, Japan would be great
Wed Sep 06, 2006 7:02 pm
Forum: Algorithms
Topic: MinCost MaxFlow code
Replies: 20
Views: 15061
Thanks for your help, now i think i understand the problem well, and solved several problems too , thanks again
Wed Aug 30, 2006 1:57 am
Forum: Algorithms
Topic: MinCost MaxFlow code
Replies: 20
Views: 15061
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 nega...
Thu Aug 24, 2006 8:40 pm
Forum: Algorithms
Topic: MinCost MaxFlow code
Replies: 20
Views: 15061

### MinCost MaxFlow code

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 learn...
Mon Jun 05, 2006 3:45 am
Forum: Volume 110 (11000-11099)
Topic: 11042 - Complex, difficult and complicated
Replies: 20
Views: 13573
What's the approach or mathematical concept required to solve this problem?
Sat Jun 03, 2006 5:46 pm
Forum: Volume 110 (11000-11099)
Topic: 11036 - Eventually Periodic Sequence
Replies: 22
Views: 6238
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