10147 - Highways

[brianfry713]

Input:

Code: Select all

2

1
1 1
0

9
1 5
0 0 
3 2
4 5
5 1
0 4
5 2
1 2
5 3
3
1 3
9 7
1 2

Correct output:

Code: Select all

No new highways need

5 7
1 6
3 7
3 8
4 9

[mahade hasan]

TLE........
help need..........

Code: Select all

#include<iostream>
#include<stdio.h>
#include<math.h>
#include<set>
#include<vector>
using namespace std;

bool Cal(bool A,bool B){
    if(A==true&&B==true) return false;
    else return true;
}
int main()
{
    int I,K,L,M,N,Tcase,P;
    float Tm;
    scanf("%d",&Tcase);
    
    for(I=0;I<Tcase;I++){
        scanf("%d",&N);
        vector<pair<int,int> >V;
        vector<int>Edge[800];
        vector<float>Cost[800];
        for(K=0;K<N;K++){
            scanf("%d %d",&L,&M);
            V.push_back(make_pair(L,M));
        }
        for(K=0;K<N;K++)
          for(L=0;L<N;L++)
             if(L!=K){
                    Tm=sqrt(((V[K].first-V[L].first)*(V[K].first-V[L].first))+((V[K].second-V[L].second)*(V[K].second-V[L].second)));\
                    Edge[K+1].push_back(L+1);
                    Edge[L+1].push_back(K+1);
                    Cost[K+1].push_back(Tm);
                    Cost[L+1].push_back(Tm);
                }
        bool Visit[800]={0},Flag=false,Road[800][800]={0},T[800]={0,1};
        scanf("%d",&M);
        L=0;
        set<pair<float,pair<int,int> > >Set;
        while(M--){
            scanf("%d %d",&P,&K);
            /*if(!Visit[P]){
                    Visit[P]=true;
                    ++L;
                }
                if(!Visit[K]){
                    Visit[K]=true;
                    ++L;
                }*/
                //Set.insert(make_pair(-10,make_pair(P,K)));
            Edge[K].push_back(P);
            Edge[P].push_back(K);
            Cost[K].push_back(-10);
            Cost[P].push_back(-10);
            
            Road[P][K]=true;
            Road[K][P]=true;
        }
        //set<pair<float,pair<int,int> > >Set;
        for(K=0;K<Edge[1].size();K++)
          Set.insert(make_pair(Cost[1][K],make_pair(1,Edge[1][K])));
          if(I>0) printf("\n");
          
          while(!Set.empty()){
                pair<int,int>Pair=Set.begin()->second;
                //printf("%f %d %d\n",Set.begin()->first,Pair.first,Pair.second);
                Set.erase(Set.begin());
                
                if(!Road[Pair.first][Pair.second]&&Cal(Visit[Pair.first],Visit[Pair.second])){
                    Road[Pair.first][Pair.second]=true;
                    Road[Pair.second][Pair.first]=true;
                    Flag=true;
                    printf("%d %d\n",Pair.first,Pair.second);
                }
                if(!Visit[Pair.first]){
                    Visit[Pair.first]=true;
                    ++L;
                }
                if(!Visit[Pair.second]){
                    Visit[Pair.second]=true;
                    ++L;
                }
                if(L==N)break;
                if(!T[Pair.second]){
                    T[Pair.second]=true;
                    for(K=0;K<Edge[Pair.second].size();K++){
                        Set.insert(make_pair(Cost[Pair.second][K],make_pair(Pair.second,Edge[Pair.second][K])));
                    }
                }
            }
            if(!Flag) printf("No new highways need\n");
    }
    return 0;
    
}

[/color]

[brianfry713]

Try using Union Find instead of set.

[TryCatchMe]

I solved this problem in not so great time using the C++ STL priority_queue data structure and Kruskal's algorithm... Kruskal's relies on using a set union data structure which is just an array that keeps track of the i_th vertex's parent in the minimum spanning tree.

Mahade-

Your nested loops have the following logic:

Code: Select all

for (i = 0 to number of points)
    for (j = 0 to number of points) //starting at the point in the 0th position in your array each time
          compute stuff

in fact, since this can be treated as an undirected graph, the loops can be tightened up a bit

Code: Select all

for (i = 0 to number of vertices - 1)
     for (j = i + 1 to number of vertices) //no need to start at 0, we already did these computations
           compute stuff

This still has the O(N^2) complexity of course, but you will probably save some time by not performing as many unnecessary computations. I hope this makes sense.

[Nazim Gazi]

Getting runtime error . Please Help.

Code: Select all

struct edge
{
    int a,b;
    double cost;
    bool operator <(const edge& p)const
    {
        return cost<p.cost;
    }
};

vector<edge>e;
int par[760];
int x[760],y[760];


int f_parent(int u)
{
    if(par[u]==u)
        return u;
     par[u]=f_parent(par[u]);
     return par[u];
}
void mst(int n)
{

    edge ed;
  int  total=1;
    int u,v;
    sort(e.begin(),e.end());
    int len=e.size();
    for(int i=0;i<len&&total<n;i++)
    {
        ed=e[i];
        u=f_parent(ed.a);
        v=f_parent(ed.b);
        if(u!=v)
        {
            total++;
            par[ed.b]=u;
            printf("%d %d\n",ed.a,ed.b);
        }

    }
}



int main()
{

   //fin;
    int t,n,m;
    scanf("%d",&t);
    while(t--)
    {

        e.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
          scanf("%d %d",&x[i],&y[i]);
        }
        for(int i=0;i<=n;i++)
            par[i]=i;
         double cost;
        edge ed;
        double r1;
            double r2;
        for(int i=n;i>1;i--)
            for(int j=i-1;j>=1;j--)
        {
            r1=abs(x[i]-x[j]);
            r2=abs(y[i]-y[j]);
            ed.a=i;
            ed.b=j;
            cost=((r1*r1)+(r2*r2));
            cost=sqrt(cost);
            ed.cost=cost;
            e.push_back(ed);
        }
        int xx,yy;
        sc("%d",&m);
        for(int i=0;i<m;i++)
        {
            scanf("%d %d",&x,&y);
            par[xx]=yy;
        }
        if(n==m+1||n==1)
            cout<<"No new highways need\n";
        else
        mst(n-m);
        pf("\n");

    }
    return 0;
}

[brianfry713]

that code won't compile

[Nazim Gazi]

Why I am getting WA . I cann't understand. Please help.

Code: Select all

#include<bits/stdc++.h>
#define MAX 800
using namespace std;

typedef pair<double,pair<int,int> > edge;
vector<edge>e;
int par[MAX];
int f_set(int x)
{
    if(par[x]==x)
        return x;
    return par[x]=f_set(par[x]);

}
bool u_set(int x,int y)
{
    int a=f_set(x);
    int b=f_set(y);
    if(a==b)
        return false;
    else
        par[a]=b;
}
void MST(int n)
{
    int total=0;
    sort(e.begin(),e.end());
    int len=e.size();
    edge ed;
    for(int i=0;i<len;i++)
    {
        ed=e[i];
        if(u_set(ed.second.first,ed.second.second))
        {
            printf("%d %d\n",ed.second.first,ed.second.second);
            total++;
            if(total==n)
                return ;

        }
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    int t,n,m,x[MAX],y[MAX];
    edge ed;
    scanf("%d",&t);
    while(t--)
    {
        e.clear();
       scanf("%d",&n);
       for(int i=1;i<=n;i++)
       {
           scanf("%d %d",&x[i],&y[i]);
       }
       double len;
       for(int i=1;i<n;i++)
       {
           for(int j=i+1;j<=n;j++)
           {
               len=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
              // cout<<len<<endl;
               ed={len,{i,j}};
               e.push_back(ed);

           }
       }
       for(int i=0;i<=n;i++)
        par[i]=i;
        scanf("%d",&m);
        int a,b;
        for(int i=0;i<m;i++)
        {
            scanf("%d %d",&a,&b);
            u_set(a,b);
        }
        if(n-m<2)
            printf("No new highways need\n");
        else
            MST(n-m-1);
        if(t)
            printf("\n");
    }
    return 0;

}

[brianfry713]

It looks like you figured it out.