10594 - Data Flow

[erfan]

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?
Any one please check it:

[rakeb]

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

[erfan]

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]

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]

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]

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?

[windows2k]

best of luck

Hello, rakeb
I get WA on the problem all the time
Would you give me some input/output ?
Thx

[filipek]

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.

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]

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.

[tat tvam asi]

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]

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]

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]

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?
Thanks in advance.

[..]

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

Thanks in advance

[Adrian Kuegel]

Did you consider the test case posted here:
http://online-judge.uva.es/board/viewtopic.php?t=4757 ?
It should break a solution that greedily removes shortest paths.