Page 1 of 1

11434 - Careless Postman Problem

Posted: Mon Mar 31, 2008 6:28 am
I am trying to solve this problem using min cost flow, but I don't quite understand the 3rd sample testcase.

Code: Select all

``````2 2
1 2 1 1 0
2 1 1 1 0
``````
Why is the result 2?
Shouldn't it be Impossible, since qi>pi?

Posted: Mon Mar 31, 2008 6:51 am
There was a clarification that the third case should be:

Code: Select all

``````2 2
1 2 1 1 1
2 1 1 1 1
``````
-----
Rio

Posted: Mon Mar 31, 2008 9:30 am
rio wrote:There was a clarification that the third case should be:

Code: Select all

``````2 2
1 2 1 1 1
2 1 1 1 1
``````
-----
Rio
Ok, now I don't understand why I keep getting WA.
Basically, I convert each edge into an edge with 0 as lower capacity and p-q as upper capacity, and I adjust the supply/demand on the vertices accordingly. I create a new source and connect it to all the supply vertices, and connect all demand vertices to the new sink.

Posted: Mon Mar 31, 2008 5:12 pm
Well, I did the same thing. And this solution has a problem.

I didn't notice that this solution is not correct until reading the discussion on the top coder forum.
It fails on case:

Code: Select all

``````1
4 6
1 2 1 1 2
2 1 1 1 2
3 4 1 1 2
4 3 1 1 2
2 4 1 0 1
3 1 1 0 1
``````
The correct answer is 8 but my code outputs 4.

Anyway, since my code got AC, the judge solution seems to did the same thing (or maybe I was just lucky).
So, I don't know where the problem is. Maybe your code is calculating the true answer. or maybe some bug in your code.
-----
Rio

Re: 11434 - Careless Postman Problem

Posted: Tue Apr 01, 2008 4:50 am
I'm starting to think that the judge input contains bugs.
I used

Code: Select all

``````assert(u>=1 && u<=n);
assert(v>=1 && v<=n);
``````
and it gave run time error.