## 11228 - Transportation System

Moderator: Board moderators

First thing: construct the graph "on the fly". There is no need to store the edges, since it is a complete graph, and the length of each edge can be calculated using the coordinates of each point.
Then, think about what Prim algorithm does, not how it is usually implemented. The implementation here is in fact easier than normally
Guru

Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

### Re: 11228 - Transportation System

I generated all edges for all pairs of cities and then used Kruskal + Union Find (with path compression and ranking)
The union find is less than 10 lines of code
Kruskal done using make_heap and pop_heap

I got WA once because I didn't realize # of states == # of railroads + 1 ........
but why is that so ?
Consider 4 cities:
4 10
0 10
0 20
0 30
0 40

The optimal way is to have 3 roads of 10 units length each.
The # of rail road is 0 but the no. of states is 2 since "0 10" and "0 40" are in two different states !

This problem is wrong, anyone else agree?
lucastan
New poster

Posts: 9
Joined: Sat Jul 02, 2011 6:46 am

### Re: 11228 - Transportation System

Hi everyone,
I'm trying to understand this problem, but i don't have in mind the reason of the correct output for some test cases, for example:

Code: Select all
`177 12330 5293 9689 3289 7071 5540 7964 1030 8062 1998 678 4257 3222 2738 152 8943 742 882 6567 2043 2295 2248 166 2586 753 9643 8593 6961 481 5384 4315 2022 3426 3533 2819 6719 798 4551 1386 018 6882 4716 30 8039 185 2265 2621 7066 9214 6546 621 4680 3286 3567 642 2914 7155 771 338 1482 7165 415 123 7722 6740 5948 8163 6345 2578 3226 8318 9645 9931 5645 3080 477 118 81`

the correct output is
Case #1: 1 597 0

But for the condition "For the purposes of this problem, consider that if the distance between any two cities is at most r then they are in the same state",taking in mind the distance between the points (2,8) and (93,96) is 126.589889 that is greater than 123 (r), i think so the correct should be Case #1 : 2 xx yy

Please, tell me what i am wrong.

Thanks

Sorry for my english.
btc
New poster

Posts: 1
Joined: Fri Dec 30, 2011 6:45 am

### Re: 11228 - Transportation System

For this input:
1
4 10
0 10
0 20
0 30
0 40

My AC code returns:
Case #1: 1 30 0

You should assume the problem meant that railroads must be greater than length r.
brianfry713
Guru

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

### Re: 11228 - Transportation System

can someone help me with the code please? my code gives the right output for all the I/O given in this thread, but gets WA. Someone help please, I've implemented Kruskal's algorithm here. Once for the individual cities(skipping the inter-state roads), another for the states(considering only the inter-state roads)

Code: Select all
`AC.Never use float as a running variable.`
Do or do not. There is no try.
Scarecrow
Learning poster

Posts: 69
Joined: Wed Oct 19, 2011 9:06 pm

### Re: 11228 - Transportation System

getting wrong answer.. . if someone could help,it would be great..thanks in advance
Code: Select all
`#include <iostream>#include <utility>#include <vector>#include <cmath>#include <algorithm>#include <cstdio>#define sqr(x) ((x)*(x))#define max 500000#define maxnode 1005using namespace std;typedef pair<float,float>ii;vector<ii>co;float round(float d){    return floor(d+0.5);}struct edges{    int s,e;    float w;};edges ed[max];int par[maxnode];bool comp(edges e1,edges e2){    return (e1.w-e2.w)<1e-9;}int findpar(int x){    if(par[x]==x)    return x;    else    return par[x]=findpar(par[x]);}int main(){    //freopen("input.txt","r",stdin);    int t,counter=0;cin>>t;    while(t!=0)    {        int n,r;        co.clear();        t--;counter++;        cin>>n>>r;        for(int i=1;i<=n;i++)par[i]=i;        for(int i=0;i<n;i++)        {            float x,y;            cin>>x>>y;            co.push_back(ii(x,y));        }        int c=-1;        for(int i=0;i<co.size();i++)        for(int j=i+1;j<co.size();j++)                {                    c++;                    ed[c].s=i+1;                    ed[c].e=j+1;                    ed[c].w=sqrt(sqr((float)co[i].first-co[j].first)+sqr((float)co[i].second-co[j].second));                }        sort(ed,ed+c+1,comp);        int s=n;        float road=0,rail=0;        for(int i=0;i<=c;i++)        {            int u=findpar(ed[i].s);            int v=findpar(ed[i].e);            if((ed[i].w-r)>1e-9 && u!=v)            {                rail+=ed[i].w;                par[v]=par[u];            }                else if(u!=v)                {                    road+=ed[i].w;                    par[v]=par[u];                    s--;                }        }        road=round(road);        rail=round(rail);        cout<<"Case #"<<counter<<": "<<s<<" "<<road<<" "<<rail<<endl;    }    return 0;}`
aowal
New poster

Posts: 1
Joined: Thu Oct 04, 2012 11:02 pm

### Re: 11228 - Transportation System

brianfry713
Guru

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

Previous