## 11434 - Careless Postman Problem

Moderator: Board moderators

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:

### 11434 - Careless Postman Problem

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?

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
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.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
``````assert(u>=1 && u<=n);