OJ Board

weighted bipartite matching can be solved by min-cost max-flow. the method looks quite similar to solving maximum cardinality matching by max-flow.

my compiler is g++ 3.4.2.

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...

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 operati...

Given the shapes of two parallelograms, how to determine whether one can be put inside the other? (NEERC 2004, Northern Subregional, Fool's Day)

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...

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!

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 ...

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...

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...