10147 - Highways

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 10147 - Highways

Post by brianfry713 » Wed Nov 07, 2012 12:49 am

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
Check input and AC output for thousands of problems on uDebug!

User avatar
mahade hasan
Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm
Location: University of Rajshahi,Bangladesh

Re: 10147 - Highways

Post by mahade hasan » Fri Jun 14, 2013 5:53 pm

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]
we r surrounded by happiness
need eyes to feel it!

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

Re: 10147 - Highways

Post by brianfry713 » Fri Jun 14, 2013 10:26 pm

Try using Union Find instead of set.
Check input and AC output for thousands of problems on uDebug!

TryCatchMe
New poster
Posts: 15
Joined: Fri May 30, 2014 12:09 am

Re: 10147 - Highways

Post by TryCatchMe » Sun Dec 28, 2014 12:32 am

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
New poster
Posts: 3
Joined: Wed Dec 10, 2014 11:23 am

Re: 10147 - Highways

Post by Nazim Gazi » Thu Jan 08, 2015 7:39 pm

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;
}
Last edited by brianfry713 on Fri Jan 09, 2015 12:09 am, edited 1 time in total.
Reason: Added code blocks

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

Re: 10147 - Highways

Post by brianfry713 » Fri Jan 09, 2015 12:10 am

that code won't compile
Check input and AC output for thousands of problems on uDebug!

Nazim Gazi
New poster
Posts: 3
Joined: Wed Dec 10, 2014 11:23 am

Re: 10147 - Highways

Post by Nazim Gazi » Sun Jan 18, 2015 7:01 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10147 - Highways

Post by brianfry713 » Mon Jan 19, 2015 9:29 pm

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 101 (10100-10199)”