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 2Code: Select all
No new highways need
5 7
1 6
3 7
3 8
4 9Code: 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;
}
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
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
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;
}
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;
}