## Search found 11 matches

Thu Oct 11, 2007 6:27 pm
Forum: Algorithms
Topic: K'th Shortest Path
Replies: 6
Views: 3433
i suppose it is the same algorithm sunny was talking about. It allows vertexes appear multiple times
Mon Oct 08, 2007 11:27 am
Forum: Algorithms
Topic: Shortest path through a given vertex
Replies: 19
Views: 7396
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.
Mon Oct 08, 2007 8:55 am
Forum: Algorithms
Topic: Shortest path through a given vertex
Replies: 19
Views: 7396
what if the graph is directed ?
Thu Aug 30, 2007 10:53 pm
Forum: Algorithms
Topic: Shortest path through a given vertex
Replies: 19
Views: 7396
I've read in a paper that there is a O(V^2) algorithm
Thu Aug 30, 2007 10:26 am
Forum: Algorithms
Topic: Shortest path through a given vertex
Replies: 19
Views: 7396

### Shortest path through a given vertex

How to find a shortest simple path from v to u that passes
through a vertex w
Fri Dec 22, 2006 10:27 am
Forum: Algorithms
Topic: Classic matrix problem
Replies: 5
Views: 2868
Is there a faster one ?
Wed Dec 20, 2006 2:43 pm
Forum: Algorithms
Topic: Classic matrix problem
Replies: 5
Views: 2868

### Classic matrix problem

Find a rectanglular submatrix of a matrix with maximum sum of its elements. What is an optimal solution for this.
Sat Sep 02, 2006 10:40 pm
Forum: Volume 110 (11000-11099)
Topic: 11080 - Place the Guards
Replies: 40
Views: 11429

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.
Sat Sep 02, 2006 9:16 pm
Forum: Volume 110 (11000-11099)
Topic: 11080 - Place the Guards
Replies: 40
Views: 11429
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.
Sat Sep 02, 2006 9:14 pm
Forum: Volume 110 (11000-11099)
Topic: 11080 - Place the Guards
Replies: 40
Views: 11429

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.
Sat Sep 02, 2006 5:20 pm
Forum: Volume 110 (11000-11099)
Topic: 11080 - Place the Guards
Replies: 40
Views: 11429

### 11080 - Place the Guards

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