## 10594 - Data Flow

Moderator: Board moderators

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:

### 10594 - Data Flow

I verify again and again but may be sample I/O for one is wrong:
input:
4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 100
output:
140
I think it should be
input:
4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 10
output:
140
Am i correct or incorrect?

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France
i think the sample i/o is ok.
see

1st we find the shortest path (according to time). the shortest path time is 7 (per unit data) and the path is(1->2->4 or 1->3->4).

here the link capacity is 100. so, we can send the whole data at the same time.

so total time for 20 unit data is = 7*20=140
so it is ok.

i solved this problem by bfs. i run bfs again and again untill D amount data is not transferred.

best of luck
Rakeb

erfan
New poster
Posts: 44
Joined: Tue Apr 15, 2003 4:31 pm
Contact:
Yah,
i was wrong.I can realize my misunderstanding.
Now i got it AC.
Actually it is a great problem
Thanks for help.

Lars Hellsten
New poster
Posts: 20
Joined: Thu Apr 10, 2003 10:53 pm

### 10594 - Bad judge data or problem statement

After wasting a fair bit of time trying to solve this using network flow, I discovered that a much simpler approach of repeatedly picking the shortest path, then deleting that path, gets AC. This is incorrect though, according to the problem description. Consider the following test case:

8 11
1 2 0
1 3 0
1 4 0
5 8 0
6 8 0
7 8 0
2 6 1
3 7 1
2 5 2
3 6 2
4 7 2
3 1

Clearly it is possible to transmit 3 units of data through this network. My incorrect (but accepted) solution attempts to push data through the edges with cost 1 initially. However, once those two paths are used and removed, there is no way to push the third data packet through the network, so it outputs "Impossible." This is totally wrong, according to the problem statement.

I guess this is why the success rate on the problem is so low.

kzaman010
Problemsetter
Posts: 18
Joined: Wed Jan 16, 2002 2:00 am
Contact:
You are right. And that's why I posted a message
not to submit it two days ago. I have already sent the updated data and
then removed the post " Not to submit".

It will be rejudged soon. Sorry for the inconvenience.

Marcin Kwiatkowski
New poster
Posts: 5
Joined: Thu Jan 01, 2004 10:43 pm
Location: Gdynia, Poland

Code: Select all

``````4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 1

``````
Why answer for this test is Impossible? Could anybody explain me that?
And one more thing...why the answer for this test case:

Code: Select all

``````4 5
1 4 1
1 3 3
3 4 4
1 2 2
2 4 5
20 10
``````
is 80?
"Imagination is more important than knowledge" Albert Einstein

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan
rakeb wrote: best of luck
Hello, rakeb
I get WA on the problem all the time
Would you give me some input/output ?
Thx

filipek
New poster
Posts: 9
Joined: Sat Jun 22, 2002 12:16 pm
Location: Poland
Contact:
Marcin Kwiatkowski wrote:

Code: Select all

``````4 4
1 3 3
3 4 4
1 2 2
2 4 5
20 1
``````
You cannot send 20 packets through this network, if edge capacity is 1 - you'll send 1 packet through 1-3-4 and one through 1-2-4, but no more.
Marcin Kwiatkowski wrote:

Code: Select all

``````4 5
1 4 1
1 3 3
3 4 4
1 2 2
2 4 5
20 10
``````
is 80?
Sending ten packets through 1-4, which takes 10 * 1 = 10 time, and 10 through 1-3-4 or 1-2-4 (whichever you want), which takes 10 * 7 = 70 time, 10 + 70 = 80.

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm
Previously this problem had a very simple solution which was infact not correct but later it was corrected by the problemsetter. And now it is not as easy as it was before. On your first thought you might think of doing something like calculating the SSSP and removing the edges and then calculate SSSP again and keep on doing so until you reach the needed amount. But the problem arises when you are provided with an input where if you remove the SSSP you can never reach the needed amount so you need to find the shortest combination making sure that you reach the target amount if it is possible.

I'd solved this problem right on the very first or second day it was added to OJ but later I got WA on correct rejudgement. Hope to solve it soon but right now I'm little busy with other things.

I hope I could make you understand what exactly is asked for in this problem. If you think your solution does that correctly and still you are getting WA then let me know, may be I'll give you some test I/O cases.
Not all of our dreams can be made to come true. But still we live with the hope to turn them into reality someday.

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm
Helo

In the first case of the sample input why it is not
possible to send the data as follows:
10 packet 1->4 (10 time unit)
10 packet 1->2->1->4 (50 time unit) ?

Peace,
Csaba Noszaly

filipek
New poster
Posts: 9
Joined: Sat Jun 22, 2002 12:16 pm
Location: Poland
Contact:
tat tvam asi wrote: 10 packet 1->4 (10 time unit)
10 packet 1->2->1->4 (50 time unit) ?
Aren't you using then edges 1-2 and 1-4 two times?

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm
Thanks Filipek!
So I can not use edges more than once. (collision???)
I did not get it from the problem's description.
Peace,
Csaba Noszaly

LittleJohn
Learning poster
Posts: 83
Joined: Wed Feb 27, 2002 2:00 am
Location: Taiwan
Dreamer#1 wrote:I'd solved this problem right on the very first or second day it was added to OJ but later I got WA on correct rejudgement. Hope to solve it soon but right now I'm little busy with other things.

I hope I could make you understand what exactly is asked for in this problem. If you think your solution does that correctly and still you are getting WA then let me know, may be I'll give you some test I/O cases.
Hello Dreamer,
I got WA on this problem, could you give me some test cases?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong
Still no one to paste some test case??
I tried to use Successive Shortest Path algorithm to solve this problem,
but gets WA. Could anyone give me the output:

Code: Select all

``````10 16
1 9 8
6 9 7
7 9 83
10 9 6
8 9 64
3 9 62
4 9 59
2 4 29
4 8 29
8 5 64
3 5 40
6 5 2
10 5 76
5 7 70
4 7 7
7 1 21
805 22349
10 18
2 1 13
10 1 54
8 1 28
3 1 88
5 1 8
7 1 86
6 1 32
4 1 75
9 1 60
4 5 8
9 5 17
6 5 55
5 3 52
2 3 50
4 3 41
3 9 66
6 9 44
10 9 35
20235 21705
10 40
4 9 13
7 9 90
9 2 76
3 2 63
2 5 83
6 5 27
5 4 21
7 4 25
1 4 74
9 1 58
7 1 64
10 1 53
5 1 80
3 1 66
6 1 5
10 4 51
6 4 86
2 4 55
8 4 40
8 1 19
2 1 92
8 10 37
5 8 26
2 8 76
6 8 23
8 3 11
4 3 12
6 3 43
7 3 10
9 3 75
5 3 33
7 6 53
10 5 59
5 7 100
7 10 52
9 10 96
3 10 44
2 10 46
5 9 73
6 9 87
9750 13344
10 38
4 9 83
5 9 52
9 7 63
1 7 30
6 7 6
2 7 48
8 7 85
10 7 4
4 7 56
3 7 21
6 1 68
2 1 98
9 1 3
3 1 12
10 1 88
4 1 31
5 1 82
8 1 15
9 2 27
8 2 67
3 2 46
4 2 95
6 2 81
5 2 14
10 2 3
3 4 39
6 4 18
10 4 89
8 4 86
5 4 67
5 3 64
8 3 7
9 3 29
5 7 50
5 8 65
10 8 20
10 3 87
6 3 54
24639 8190
10 11
6 3 53
9 3 4
5 3 44
3 4 55
8 4 71
6 4 43
1 4 86
2 4 89
9 4 8
5 4 89
10 4 96
4972 23026
10 0
26969 1206
10 39
9 4 13
10 4 98
1 4 68
5 4 95
8 4 92
2 1 3
9 1 47
8 1 7
6 1 72
7 1 10
1 10 48
5 10 90
3 5 78
8 5 54
7 5 8
9 5 72
2 5 12
1 5 78
6 5 87
2 3 95
10 2 60
8 2 16
2 6 25
7 6 45
6 10 36
7 10 8
3 1 39
4 2 1
9 2 61
7 2 49
6 8 42
10 8 13
3 7 70
9 10 81
3 10 23
3 8 27
7 8 18
9 8 78
3 9 40
32702 15084
10 9
9 5 49
2 5 1
5 6 75
2 6 5
10 6 6
9 6 23
7 6 25
1 6 45
3 6 40
4124 28230
10 37
2 6 44
6 7 4
5 7 12
3 7 36
10 7 47
8 7 61
2 7 43
5 6 72
3 6 27
6 10 61
5 10 9
4 10 75
10 8 56
6 8 83
4 8 13
5 8 93
2 8 82
3 8 26
1 3 57
4 3 96
9 3 66
5 3 57
2 3 93
10 3 19
9 7 69
1 7 8
4 7 64
9 5 66
5 2 49
1 2 12
4 2 1
9 2 48
2 10 24
9 10 7
6 9 57
1 9 13
8 9 50
22137 19596
10 11
4 9 66
2 9 36
3 9 97
7 9 41
5 9 88
1 9 49
6 9 94
8 9 14
10 9 80
5 4 78
7 5 7
19920 24127
``````
My output:

Code: Select all

``````11270
1092690
516750
841452
904904
Impossible.
694824
210324
465609
2569680
``````
My signature: