10842 - Traffic Flow

[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.

[Dreamer#1]

Think of MST.

[Eduard]

Thanks.
Now I understand why during online contest so many people solved this problem.

[Larry]

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

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

[Martin Macko]

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

[artem]

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

[helloneo]

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

[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.

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

[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.

Code: Select all

//removed after AC

Plz help(Sugg,I/Os... anything)

-Shihab

[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

[shihabrc]

Thanx a lt. Got AC. I really missed that point.

[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...

[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