KruskalvsBor?vka

#define sizex 100000000
#include
#include
#include
#include
#include
#include
using namespace std;
int *data,res;
long long mytic(){
long long result = 0.0;
struct timeval tv;
gettimeofday( &tv, NULL );
result = ((long long)tv.tv_sec)*1000000 + (long long)tv.tv_usec;
return result;
}
#define dic1() disA(generator)
#define dic2() disB(generator)
struct edge{int a,b,w;};
bool cmp(edge a,edge b){
return a.w}
#define foredge for(int i=0;i#define forvert2 for(int i=0;i#define eg gr.E[i]
struct graph{
int N,El;
edge E[50000000];
void sorter(){
sort(E,E+El,cmp);
}
void genData(int a,int b){
N=a;
El=b;
mt19937 generator;
uniform_int_distribution disA(0,N-1);
uniform_int_distribution disB(0,21474836);
for(int i=0;i E[i].a=dic1();
while((E[i].b=dic1())==E[i].a);
E[i].w=dic2();
}
}
} gr;
struct ds_set{
int fa[10000000];
void clear(){
for(int i=0;i }
int find(int p){return ~fa[p]?fa[p]=find(fa[p]):p;}
inline int merge(int a,int b){return (a==b)?(-1):(fa[b]=a);}
} ds;
#define ffind(a) ds.find(a)
#define funion(a,b) ds.merge(a,b)
struct algo_Kruskal{
long long run(){
long long ans=0;
gr.sorter();
int a,b;
foredge{
a=ffind(eg.a),b=ffind(eg.b);
ans+=~funion(a,b)?eg.w:0;
}
return ans;
}
} Kruskal;
struct algo_Boruvka{
struct v{
int a,p;
} vm[10000000];
long long run(){
long long ans=0;
int a,b,c,w;
while(1){
c=0;
forvert2 vm[i].a=100000000;
foredge{
w=eg.w,a=ffind(eg.a),b=ffind(eg.b);
if(a==b) continue;
++c;
if(w if(w }
if(!c) break;
forvert2 if(vm[i].a!=100000000) {
a=ffind(gr.E[vm[i].p].a);
vm[i].p=ffind(gr.E[vm[i].p].b);
ans+=(~funion(a,vm[i].p))?vm[i].a:0;
}
}
return ans;
}
} Boruvka;
FILE* loggar;
void testN(){
long long i;
printf("Kruskal method\n");
fprintf(loggar,"Kruskal method\n");
ds.clear();
long long start=mytic();
i=Kruskal.run();
start=mytic()-start;
printf("%lld\n",i);
printf("Time usage: %lld us\n",start);
fprintf(loggar,"%lld\n",i);
fprintf(loggar,"Time usage: %lld us\n",start);
}
void testU(){
long long i;
printf("Bor(uc)uvka method\n");
fprintf(loggar,"Bor(uc)uvka method\n");
ds.clear();
long long start=mytic();
i=Boruvka.run();
start=mytic()-start;
printf("%lld\n",i);
printf("Time usage: %lld us\n",start);
fprintf(loggar,"%lld\n",i);
fprintf(loggar,"Time usage: %lld us\n",start);
}
int as[15]={200 ,500 ,1000 ,2000 ,5000 ,10000 ,10000 ,20000 ,50000 ,100000 ,300000 ,500000 ,1000000 ,5000000 ,10000000};
int bs[15]={1000,3000,10000,50000,100000,300000,500000,1000000,1000000,1000000,2000000,6000000,10000000,50000000,50000000};
int main(){
int a,b,c,i,j,k,l,m,n,N,U,P,UP;
loggar=fopen("MSTTest.data","w");
for(int i=0;i<15;++i){
printf("%d %d\n",as[i],bs[i]);
fprintf(loggar,"V=%d,E=%d\n",as[i],bs[i]);
gr.genData(as[i],bs[i]);
testN(),testU();
}
fclose(loggar);
return 0;
}