10842 - Traffic Flow

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

10842 - Traffic Flow

Post by Eduard » Tue May 10, 2005 10:40 am

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.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

User avatar
Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

Post by Dreamer#1 » Tue May 10, 2005 11:04 am

Think of MST. :)

Eduard
Experienced poster
Posts: 183
Joined: Fri Sep 26, 2003 2:54 pm
Location: Armenia,Yerevan

Post by Eduard » Tue May 10, 2005 12:55 pm

Thanks.
Now I understand why during online contest so many people solved this problem.
someone who like to solve informatic problems.
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:29650

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Tue May 10, 2005 3:08 pm

To be more specific, you can think of it as BST. Err.. that's Bottleneck Spanning Tree.

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

10842 - Traffic Flow

Post by artem » Sat Aug 13, 2005 8:38 pm

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???

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: WA in 10842

Post by Martin Macko » Tue Aug 16, 2005 8:45 am

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 :wink: . I am constructing MST, too. You probably have a bug in the code...

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

Post by artem » Tue Aug 16, 2005 5:38 pm

Thank you Martin for reply. You is right, i find bug in my code, and got AC.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

10842 - Traffic Flow

Post by helloneo » Fri Nov 18, 2005 6:04 pm

Code: Select all

CUT AFTER AC
my approach is MST ( maximum spanning tree )
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.

tan_Yui
Experienced poster
Posts: 155
Joined: Sat Jul 10, 2004 12:41 am

Re: 10842 Traffic Flow ..

Post by tan_Yui » Tue Nov 22, 2005 7:16 am

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.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Tue Nov 22, 2005 10:43 am

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.. ^^;

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

10842 Traffic Flow. -----Stuck in traffic jam(WA)

Post by shihabrc » Wed Jan 18, 2006 12:58 am

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.

Code: Select all

//removed after AC
Plz help(Sugg,I/Os... anything)

-Shihab
Last edited by shihabrc on Wed Jan 18, 2006 5:08 pm, edited 1 time in total.
Shihab
CSE,BUET

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Post by helloneo » Wed Jan 18, 2006 4:34 am

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

shihabrc
New poster
Posts: 49
Joined: Sun Sep 18, 2005 10:20 am
Location: CSE,BUET
Contact:

Post by shihabrc » Wed Jan 18, 2006 5:07 pm

Thanx a lt. Got AC. I really missed that point. :oops:
Shihab
CSE,BUET

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

Explanation please :)

Post by nymo » Wed Dec 27, 2006 3:29 pm

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...
regards,
nymo

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

Re: 10842 - Traffic Flow

Post by Chirag Chheda » Fri Feb 27, 2009 9:34 pm

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

Post Reply

Return to “Volume 108 (10800-10899)”