10147 - Highways

Moderator: Board moderators

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

Re: 10147 - Highways

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!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

Re: 10147 - Highways

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

}
//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());

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

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

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.

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

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.

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

Re: 10147 - Highways

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

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

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