Page 1 of 2
10842 - Traffic Flow
Posted: Tue May 10, 2005 10:40 am
by Eduard
Hello.
I want to know what algorith are you using for this problem.I think this problem must have easy solution but I solve it only using binary search.
I want to know have someone else solved this problems using binary search.
Thanks
Eduard.
Posted: Tue May 10, 2005 11:04 am
by Dreamer#1
Think of MST.
Posted: Tue May 10, 2005 12:55 pm
by Eduard
Thanks.
Now I understand why during online contest so many people solved this problem.
Posted: Tue May 10, 2005 3:08 pm
by Larry
To be more specific, you can think of it as BST. Err.. that's Bottleneck Spanning Tree.
10842 - Traffic Flow
Posted: Sat Aug 13, 2005 8:38 pm
by artem
Hi all,
I use to slove this problem MST and get WA all time.
If there are some bad inputs for this problem or I mistake with choose algoritm???
Re: WA in 10842
Posted: Tue Aug 16, 2005 8:45 am
by Martin Macko
artem wrote:Hi all,
I use to slove this problem MST and get WA all time.
If there are some bad inputs for this problem or I mistake with choose algoritm???
Your approach looks good
. I am constructing MST, too. You probably have a bug in the code...
Posted: Tue Aug 16, 2005 5:38 pm
by artem
Thank you Martin for reply. You is right, i find bug in my code, and got AC.
10842 - Traffic Flow
Posted: Fri Nov 18, 2005 6:04 pm
by helloneo
my approach is MST ( maximum spanning tree )
it is ok for sample inputs..
but getting WA..
what should i think about..?
Re: 10842 Traffic Flow ..
Posted: Tue Nov 22, 2005 7:16 am
by tan_Yui
I used Minimum Spanning Tree.
I think :
--- there may be several roads which connect same cities.
--- there may be several roads where the starting point and the terminal are the same. ... like a rotary.
First case is like :
1 2 59
1 2 65
And second case is like :
0 0 900
0 0 800
0 0 950
Try to check following input :
Code: Select all
6
2 3
0 1 10
0 1 20
0 0 30
4 5
0 1 1
3 1 2
1 2 3
2 3 4
0 2 5
1 3
0 0 900
0 0 800
0 0 950
3 2
1 0 100
2 0 115
7 9
0 1 50
0 2 60
1 3 120
1 4 90
2 5 50
3 5 80
3 6 70
4 6 40
5 6 140
4 8
0 1 50
0 2 60
1 1 20
1 2 59
1 2 65
1 3 60
2 3 62
3 0 45
Output :
Code: Select all
Case #1: 20
Case #2: 3
Case #3: 950
Case #4: 100
Case #5: 50
Case #6: 60
Best regards.
Posted: Tue Nov 22, 2005 10:43 am
by helloneo
Thanks~! I got AC..~
My approach was OK.. But I did a stupid mistake sorting edges.. and didn't know how to handle the edges coming to same cities..
I really appreciate it.. ^^;
10842 Traffic Flow. -----Stuck in traffic jam(WA)
Posted: Wed Jan 18, 2006 12:58 am
by shihabrc
I've used MAXIMUM spanning tree 2 solve. But I'm gettin WA. I've tested several types of Inputs. But cannot find out why WA. Plz Somebody hlp.
Plz help(Sugg,I/Os... anything)
-Shihab
Posted: Wed Jan 18, 2006 4:34 am
by helloneo
Code: Select all
for(i=0;i<E;i++){
scanf("%d %d %d",&a,&b,&c);
if(mat[a][b]<c) mat[a][b]=c;
}
the road is bidirectional (maybe)
so try like this..
mat[a]
= mat[a] = c;
and don't forget to initialize mat
Posted: Wed Jan 18, 2006 5:07 pm
by shihabrc
Thanx a lt. Got AC. I really missed that point.
Explanation please :)
Posted: Wed Dec 27, 2006 3:29 pm
by nymo
Problem statement says:
Code: Select all
They want to do it in such a way that the minimum capacity among all of the remaining roads is as large as possible.
I am afraid that I don't understand the meaning... Can someone explain it with the second test case?
... Thanks in advance...
Re: 10842 - Traffic Flow
Posted: Fri Feb 27, 2009 9:34 pm
by Chirag Chheda
Can someone please explain me the output of the second case? I am having a really hard time understanding this problem. Any help would be appreciated
4 5
0 1 1
3 1 2
1 2 3
2 3 4
0 2 5