OJ Board

i suppose it is the same algorithm sunny was talking about. It allows vertexes appear multiple times

it does matter. Consider graph: v --> w --> u, then we have only (v_out, w_in), (w_out, u_in) (v_out, t) (u_out, t) edges all with capacity 1 and (s, w_out, 2) - no flow of size 2 exists, but the required path does.

what if the graph is directed ?

Thanks for quick reply.
I've read in a paper that there is a O(V^2) algorithm

How to find a shortest simple path from v to u that passes
through a vertex w

Is there a faster one ?

Find a rectanglular submatrix of a matrix with maximum sum of its elements. What is an optimal solution for this.

I programmed maximum matching and was sure it is correct, but can not get my solution AC. Wish i new what is my problem and why there were so many resubmitions during the contest.

mamun wrote:Input

Code: Select all

3
5 2
0 1
2 3
5 3
0 1
2 3
1 3
4 3
2 0
2 1
2 3

Output

Code: Select all

3
3
1

Getting same results. Could some1 give an example of a solution that gets ACCEPTED.

Nazmul Quader Zinnuree wrote:Input

Code: Select all

5
1 0
2 0
3 2
1 2
2 3
3 3
1 2
2 3
1 3
13 10
0 5
5 4
5 3
5 2
5 1
5 6
7 8
7 9
7 10
7 11

Output

Code: Select all

1
2
1
-1
3

I guess there is some error as examples 3 and 4 contain vertex number out of range. All other tests pass.

Getting WA. Could you give some 'tricky' tests ?