I've used O(n^2) for the connections too and got accepted. But I'm not happy with my running time.Sedefcho wrote:Yes, I consider all the connections, it's O(N^2), right. I justCode: Select all
Do you consider every possible connection between the nodes? That's O(n^2)!
use the standard Kruskal's algorithm, that's why I was so
sure I have to get ACC.
How?? What you have changed in the code?asmaamagdi wrote:Thank u guys for ur help. I was giving up this problem but I got it ACed finally
Which double variable you change to int??sakhassan wrote:Thanks. But malloc doesn't bother me ..... I change my double variable to int and got AC ... I don't know why double makes trouble
used the union find algorithm.How?? What you have changed in the code?
Code: Select all
#include<iostream>
#include<vector>
#include<algorithm>
#include<cmath>
#include<iomanip>
using namespace std;
bool f[1000];
vector<int> v,w;
vector< vector<int> > cn;
void fn(int k){
int i,j,n;
for(i=0;i<cn[k].size();i++){
n=cn[k][i];
if(f[n]){
f[n]=0;
j=0;
while(w[j]!=n) j++;
w.erase(w.begin()+j);
v.push_back(n);
fn(n);
}
}
}
int main(){
int n,m,c[1000][2],i,j,p,p1,p2;
int mn,d;
double ans;
while(cin>>n){
for(i=1;i<=n;i++){
cin>>c[i][0]>>c[i][1];
f[i]=1;
}
cin>>m;
cn.clear();
cn.resize(n+1);
while(m--){
cin>>i>>j;
cn[i].push_back(j);
cn[j].push_back(i);
}
v.clear();w.clear();
v.push_back(1);
for(i=2;i<=n;i++)
w.push_back(i);
f[1]=0;
fn(1);
ans=0.0;
while(w.size()>0){
mn=(c[v[0]][0]-c[w[0]][0])*(c[v[0]][0]-c[w[0]][0])+(c[v[0]][1]-c[w[0]][1])*(c[v[0]][1]-c[w[0]][1]);
p1=v[0];p2=w[0];
p=0;
for(i=0;i<v.size();i++){
for(j=0;j<w.size();j++){
d=(c[v[i]][0]-c[w[j]][0])*(c[v[i]][0]-c[w[j]][0])+(c[v[i]][1]-c[w[j]][1])*(c[v[i]][1]-c[w[j]][1]);
if(d<mn){
mn=d;
p1=v[i];p2=w[j];
p=j;
}
}
}
ans+=sqrt(1.0*mn);
f[w[p]]=0;
fn(p2);
v.push_back(w[p]);
w.erase(w.begin()+p);
}
cout<<setiosflags(ios::fixed)<<setprecision(2)<<ans<<endl;
}
return 0;
}
Code: Select all
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX_V 1000
typedef struct { int v1; int v2; float cost; } edge;
typedef struct point { int x; int y; } point;
edge edges[MAX_V];
point buildings[MAX_V];
int set[MAX_V];
int rank[MAX_V];
int compare (const void * a, const void * b) {
float cost_a = ((edge*) a)->cost, cost_b = ((edge*) b)->cost;
if(cost_a > cost_b) return 1;
else if(cost_a == cost_b) return 0;
else return -1;
}
void link(int a, int b) {
if(rank[a]>rank[b])
set[b]=a;
else {
set[a]=b;
if(rank[a]==rank[b])
rank[b]++;
}
}
int find(int a) {
if(set[a]!=a)
set[a]=find(set[a]);
return set[a];
}
int main (int argc, const char * argv[]) {
//freopen("input.txt", "rb", stdin);
//freopen("output.txt", "wb", stdout);
int num_buildings = -1, num_pipes = -1;
while (scanf("%d%*c", &num_buildings) == 1) {
int num_edges = 0;
for (int i=0; i<num_buildings; i++) {
scanf("%d %d%*c", &buildings[i].x, &buildings[i].y);
set[i]=i;
rank[i]=0;
}
for (int i=0; i<num_buildings; i++) {
for (int k=i+1; k<num_buildings; k++) {
edges[num_edges].v1 = i;
edges[num_edges].v2 = k;
edges[num_edges].cost = sqrt(pow((float) (buildings[i].x-buildings[k].x), 2) + pow((float) (buildings[i].y-buildings[k].y), 2));
num_edges++;
}
}
scanf("%d%*c", &num_pipes);
for (int i = 0, start, end; i<num_pipes; i++) {
scanf("%d %d%*c", &start, &end);
if (start >= 1 && end >= 1)
link(find(start-1), find(end-1));
}
qsort(edges, num_edges, sizeof(edge), compare);
float minCost = 0;
for (int i=0; i<num_edges; i++) {
int v1 = find(edges[i].v1), v2 = find(edges[i].v2);
if (v1 != v2) {
link(v1, v2);
minCost += edges[i].cost;
}
}
printf("%.2f\n", minCost);
}
return 0;
}
There's almost 300000 edges in the worst case, not 1000.Code: Select all
#define MAX_V 1000 ... edge edges[MAX_V];
Hi some one PLZ help me
i solve 10147 same as this problem
but i got WA in 10397
Code: Select all
CUT after ACC................. :lol: :lol:
Some PLZ help me................
I solve this problem same code as i post here
the problem was double
i change the double type to int then it got acc.......
But what is wrong with double.?????????
Code: Select all
#include<iostream>
#include<math.h>
using namespace std;
long n,m,i,j,f,t,p[10000];
double extra;
struct edge
{
long from;
long to;
double dist;
}edg[1000000];
struct node
{
long x;
long y;
}nod[10000];
long parent(long u)
{
if(p[u]==-1) return u;
else
{
p[u]=parent(p[u]);
return p[u];
}
}
int fn(const void *a,const void *b)
{
edge *x=(edge *)a;
edge *y=(edge *)b;
if(x->dist-y->dist>0.00) return 1;
if(x->dist-y->dist>0.00) return -1;
return 0;
}
void FIND_MST()
{
qsort(edg,n*n,sizeof(edg[0]),fn);
for(i=0;i<n*n;i++)
{
if(parent(edg[i].from)!=parent(edg[i].to))
{
extra
+=edg[i].dist;
p[parent(edg[i].from)]=parent(edg[i].to);
}
}
}
int main()
{
double aa,aaa;
while(scanf("%ld",&n)!=EOF)
{
for(i=0;i<n;i++)
{
p[i]=-1;
cin>>f>>t;
nod[i].x=f+10000;
nod[i].y=t+10000;
}
cin>>m;
for(i=0;i<m;i++)
{
cin>>f>>t;
edg[(f-1)*n+t-1].from=f-1;
edg[(f-1)*n+t-1].to=t-1;
p[parent(edg[(f-1)*n+t-1].from)]=parent(edg[(f-1)*n+t-1].to);
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
edg[(i*n)+j].from=i;
edg[(i*n)+j].to=j;
if(i==j)
{
edg[(i*n)+j].dist=0.00;
}
else
{
edg[(i*n)+j].dist=sqrt((nod[i].x-nod[j].x)*(nod[i].x-nod[j].x)+(nod[i].y-nod[j].y)*(nod[i].y-nod[j].y));
}
}
}
extra=0.00;
FIND_MST();
printf("%.2lf\n",extra);
}
return 0;
}