10842  Traffic Flow
Moderator: Board moderators
10842  Traffic Flow
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.
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.
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
Thanks.
Now I understand why during online contest so many people solved this problem.
Now I understand why during online contest so many people solved this problem.
someone who like to solve informatic problems.
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650
http://acm.uva.es/cgibin/OnlineJudge?AuthorInfo:29650

 Guru
 Posts: 647
 Joined: Wed Jun 26, 2002 10:12 pm
 Location: Hong Kong and New York City
 Contact:
To be more specific, you can think of it as BST. Err.. that's Bottleneck Spanning Tree.
Check out http://www.algorithmist.com !
10842  Traffic Flow
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???
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???

 A great helper
 Posts: 481
 Joined: Sun Jun 19, 2005 1:18 am
 Location: European Union (Slovak Republic)
Re: WA in 10842
Your approach looks good . I am constructing MST, too. You probably have a bug in the code...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???
10842  Traffic Flow
Code: Select all
CUT AFTER AC
it is ok for sample inputs..
but getting WA..
what should i think about..?
Last edited by helloneo on Tue May 22, 2007 8:00 am, edited 2 times in total.
Re: 10842 Traffic Flow ..
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 :
Output :
Best regards.
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
Code: Select all
Case #1: 20
Case #2: 3
Case #3: 950
Case #4: 100
Case #5: 50
Case #6: 60
10842 Traffic Flow. Stuck in traffic jam(WA)
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
Code: Select all
//removed after AC
Shihab
Last edited by shihabrc on Wed Jan 18, 2006 5:08 pm, edited 1 time in total.
Shihab
CSE,BUET
CSE,BUET
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;
}
so try like this..
mat[a] = mat[a] = c;
and don't forget to initialize mat
Explanation please :)
Problem statement says:
I am afraid that I don't understand the meaning... Can someone explain it with the second test case?
... Thanks in advance...
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.
... Thanks in advance...
regards,
nymo
nymo

 Learning poster
 Posts: 74
 Joined: Sat Jun 21, 2008 12:24 pm
 Location: India
Re: 10842  Traffic Flow
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
4 5
0 1 1
3 1 2
1 2 3
2 3 4
0 2 5