## 11733 - Airports

Moderator: Board moderators

### 11733 - Airports

I can not find my wrong in simple MST problem

MRH
Learning poster

Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

### Re: 11733 - Airports

Hi try this input checking.. its help u i think..
4
3 2 120
1 2 20
2 3 120
5 2 100
1 3 20
3 5 100
5 2 120
1 3 20
3 5 100
4 3 10
1 2 5
2 3 15
3 4 0
Case #1: 260 2
Case #2: 420 4
Case #3: 480 3
Case #4: 25 2
ASU(SUST)
"Teme jabo bole to Shopno deki ni"
robot
New poster

Posts: 29
Joined: Sun May 24, 2009 8:39 pm

### Help in understanding 11733 - Airports

Hi,

i m having difficulty in understanding the theme of this problem, at first i thought it can b solved by using kruskal and union find... but the sample i/o given below is not fitting to my logic...

5 2 100
1 3 20
3 5 100

here there are link between 1 -> 3 -> 5 so i consider it whole as 1, there are two more locations 2 and 4 so all together it became 1 + 1 + 1 = 3 airports...... but how the correct number of airports became 4 ??? please clarify me ....

sory 4 my bad English .....
anis_cuet016
New poster

Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

### Re: 11733 - Airports

Well, indeed this can be solved by kruskal, but you have misunderstood the problem. Problem clearly said
The government now needs your help to decide on the cheapest way of ensuring that every location has access to an airport. The aim is to make airport access as easy as possible, so if there are several ways of getting the minimal cost, choose the one that has the most airports.

So, it you look closely, when you build the MST, you have larger edges at the end. Say, the last edge cost is A and airport building cost is B where A > B, so clearly, you would like not to build this road, rather, you will build an airport more. As you are putting just one airport in each tree of the minimum spanning forest, it is clear from the tree property that, if you remove an edge from it, it will be split into two trees.... So, previously you built one airport for the tree, and if the above property holds, you would cut this road, and then you have to build one more airport.

I think now you understand the problem.
You should not always say what you know, but you should always know what you say.
zobayer
Experienced poster

Posts: 110
Joined: Tue May 06, 2008 2:18 pm

### Re: 11733 - Airports

Thankz a lot zobayer ......... what kind of shit i m, didnt give proper concentration in that para, i think i should b more carefull....... nwayz just added this line in my code and got accepted nthing else changed

Code: Select all
`if(G[i].wt < weight)// blah blah blah ......`

Hey buddy thankz again, was stuck in this problem for more then two week ..........
Khodahafiz
Anis
anis_cuet016
New poster

Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

### Re: 11733 - Airports

try this:

Code: Select all
`18 7 101 3 51 2 82 4 63 4 104 5 305 6 65 7 15`

Code: Select all
`Case #1: 65 4`
Shafaet_du
Experienced poster

Posts: 147
Joined: Mon Jun 07, 2010 11:43 am

### Re: 11733 - Airports

Hi help me pls i cannot find the WA
tell pls if i misunderstood the problem or gimme a critical Input pls
Code: Select all
`#include "stdafx.h"#include<string>#include<stdio.h>#include<vector>#include<string.h>#include<utility>#include<queue>using namespace std;vector<int> pset(100000);int findSet(int i) {   return (pset[i] == i) ? i :      (pset[i] = findSet(pset[i]));}void initSet(int _size) {   pset.clear();      pset.resize(_size);   for (int i=0; i<_size;i++)       pset[i]=i;}void unionSet(int i, int j) {   pset[findSet(i)]=findSet(j);}bool isSameSet(int i, int j) {   return findSet(i)==findSet(j);}typedef pair<int,pair<int,int> > iii;priority_queue < iii , vector < iii > , greater < iii > > edgeList;int kruskal(int n) { // n = #vertices, m= #aristas, retorna valor MST.   int cont = 0; double mst_cost =  0;   initSet(n);   while(!edgeList.empty() && cont < n-1)    {      iii front = edgeList.top(); edgeList.pop();      if ( !isSameSet(front.second.first,front.second.second) ) // nodo a y b      {         cont++;        mst_cost += front.first;          unionSet(front.second.first,front.second.second);      }   }   return mst_cost;}int casos,vertices,aristas,aero;int ori,des,pes;int main(){   freopen("in.txt","rt",stdin);   freopen("out.txt","wt",stdout);   scanf("%d",&casos);   for(int c=0;c<casos;c++)   {      while(!edgeList.empty())         edgeList.pop();      scanf("%d %d %d",&vertices,&aristas,&aero);// aero= costo por creaeaeropuerto      for(int a=0;a<aristas;a++)      {         iii coso;         scanf("%d %d %d",&ori,&des,&pes);         if(pes<aero)         {            coso.first=pes;coso.second.first=ori-1;coso.second.second=des-1;//ORIgen DEStino PESo            edgeList.push(coso);         }      }      int rpta=kruskal(vertices);      for(int i=0;i<vertices;i++)         findSet(i);      int buliano=0;      for(int i=0;i<vertices;i++)      for(int j=0;j<i;j++)      {         if(pset[i]==pset[j])         {            buliano++;            break;         }      }      rpta+=(aero*(vertices-buliano));//vertices - buliano = cantidad de aeropuertos      printf("Case #%d: %d %d\n",c+1,rpta,vertices-buliano);   }   return 0;}`
spewer
New poster

Posts: 4
Joined: Tue Dec 20, 2011 4:04 pm

### Re: 11733 - Airports

remove the lines:
#include "stdafx.h"
freopen("in.txt","rt",stdin);
freopen("out.txt","wt",stdout);
brianfry713
Guru

Posts: 1870
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11733 - Airports

OMG! Solved it with JAVA in 0.892.

But its really frustrating... had this code first:
Code: Select all
`if(i != t - 1) out.printf("Case #%d: %d %d\n", i + 1, totalCost + (long)used.cardinality() * a, used.cardinality());else out.printf("Case #%d: %d %d", i + 1, totalCost + (long)used.cardinality() * a, used.cardinality());`

Got WAs...

changed to:
Code: Select all
`//if(i != t - 1) out.printf("Case #%d: %d %d\n", i + 1, totalCost + (long)used.cardinality() * a, used.cardinality());//else out.printf("Case #%d: %d %d", i + 1, totalCost + (long)used.cardinality() * a, used.cardinality());`

Got AC...

but problem statement clearly says:
Your program should output exactly T lines, one for each case.
SyFy
New poster

Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm

### Re: 11733 - Airports

You should print a newline at the end of the last line on most problems.
brianfry713
Guru

Posts: 1870
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11733 - Airports

does it matter for instance if I will print 2 newlines ? and how can I know that when I am getting WAs in JAVA its not PE ?
brianfry713 wrote:You should print a newline at the end of the last line on most problems.
SyFy
New poster

Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm

### Re: 11733 - Airports

Yes it matters how many newlines you print. Don't count on ever getting PE. On a lot of problems extra or missing whitespace will give you WA.
brianfry713
Guru

Posts: 1870
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11733 - Airports

yep. but its very sad when you get WA and dont know whats wrong: algo or output.

brianfry713 wrote:Yes it matters how many newlines you print. Don't count on ever getting PE. On a lot of problems extra or missing whitespace will give you WA.
SyFy
New poster

Posts: 13
Joined: Tue Jun 19, 2012 12:16 pm

### Who is online

Users browsing this forum: No registered users and 1 guest