11228 - Transportation System

[Adrian Kuegel]

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

[lucastan]

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?

[btc]

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

1
77 123
30 52
93 96
89 32
89 70
71 55
40 79
64 10
30 80
62 19
98 67
8 42
57 32
22 27
38 1
52 89
43 74
2 8
82 65
67 20
43 22
95 22
48 16
6 25
86 75
3 96
43 85
93 69
61 4
81 53
84 43
15 20
22 34
26 35
33 28
19 67
19 79
8 45
51 13
86 0
18 68
82 47
16 3
0 80
39 18
5 22
65 26
21 70
66 92
14 65
46 6
21 46
80 32
86 35
67 6
42 29
14 71
55 77
1 3
38 14
82 71
65 41
5 12
3 77
22 67
40 59
48 81
63 63
45 25
78 32
26 83
18 96
45 99
31 56
45 30
80 47
7 1
18 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.

[brianfry713]

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.

[Scarecrow]

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.


[aowal]

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 1005

using 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;
}


[brianfry713]

Use double instead of float.