Search found 10 matches

by frk_styc
Sat Mar 25, 2006 11:27 pm
Forum: Algorithms
Topic: Weighted bipartite matching?
Replies: 10
Views: 4653

weighted bipartite matching can be solved by min-cost max-flow. the method looks quite similar to solving maximum cardinality matching by max-flow.
by frk_styc
Fri Dec 09, 2005 12:17 pm
Forum: C++
Topic: why programs that compile well keep getting ce here???
Replies: 4
Views: 2134

why programs that compile well keep getting ce here???

my compiler is g++ 3.4.2.
by frk_styc
Fri Jun 17, 2005 6:54 pm
Forum: Algorithms
Topic: Josephus problem modified
Replies: 1
Views: 1090

Re: Josephus problem modified

Hi, There are 2n people sitting in a circle . The first n are good and next n are bad. Now i have to choose minimum k such that all the bad n are eliminated before the first n. How do i find such k. Please point me to links or documents ? Is there any recursive formula ? Regards, Terry a problem fr...
by frk_styc
Sat May 28, 2005 4:24 pm
Forum: Algorithms
Topic: Prime number
Replies: 3
Views: 1269

To avoid overflow you may use the following code: I64 mod_mul(I64 x,I64 y,I64 n) { if(!x) return 0; return (((x&255)*y)%n+(mod_mul(x>>8,y,n)<<8)%n)%n; } The function shown above computes (x * y) % n. But in my practice I prefer implementing full-precision 64-bit multiplication and module operations ...
by frk_styc
Sun May 22, 2005 2:34 pm
Forum: Algorithms
Topic: A problem about parallelograms
Replies: 0
Views: 648

A problem about parallelograms

Given the shapes of two parallelograms, how to determine whether one can be put inside the other? (NEERC 2004, Northern Subregional, Fool's Day)
by frk_styc
Sun May 22, 2005 2:30 pm
Forum: Algorithms
Topic: BeiJing 2004 : Color a Tree
Replies: 1
Views: 1158

Actually some hint has been given in Chinese in the Discuss page but perhaps you are unable to read it, so I will explain it here. What the problem demands is to find a permutation of {C_i} that satisfies some constraints such that the sum Sigma (k = 1->N) { k * C_i_k } is minimal. Suppose we've fou...
by frk_styc
Thu May 05, 2005 3:35 pm
Forum: Volume 7 (700-799)
Topic: 753 - A Plug for UNIX
Replies: 20
Views: 10555

mf wrote:There can be more than 300 plug names in the input - each of the 100 adapters may introduce up to two new plug names. Increase your MAX constant to something like a 500.

Also, your program does not print a blank line between test cases.
Oh I see! Now it's been accepted. Thank you very very much!
by frk_styc
Thu May 05, 2005 11:37 am
Forum: Volume 7 (700-799)
Topic: 753 - A Plug for UNIX
Replies: 20
Views: 10555

753 - A plug for UNIX

I use the highest-label preflow-push algorithm for max flow. To find the node with the "highest-label" I use a heap (push_heap & pop_push from STL with a Less functor for key comparison). My submissions all end up with a runtime error (SIGSEGV). After checking many times I still can't find the code ...
by frk_styc
Mon Apr 18, 2005 5:28 pm
Forum: Algorithms
Topic: quentions about a knapsack problem
Replies: 2
Views: 993

Thanks! I've found the key to the problem. First, the division in the inner loop of my code takes too much time. It's completely unnecessarily to do such a division. Second, counting can be done during the process of DP, this saves an additional loop and provides the possibility to end the outer loo...
by frk_styc
Sun Apr 17, 2005 5:37 pm
Forum: Algorithms
Topic: quentions about a knapsack problem
Replies: 2
Views: 993

quentions about a knapsack problem

I'm now trying to solve a knapsack problem but find that an ordinary DP is too slow to handle it. A detailed description is: There are N<=100 types of objects whose values lie between 1 and 1000. To fill a knapsack of volume M<=100000, at most c_i<=1000 of the ith type can be selected. Calculate how...

Go to advanced search