- 繁忙的都市
- 2016-07-17 11:55:29 @
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
int a[10010]={0},x[10010]={0},y[10010]={0},w[10010]={0};
int n,m,p=0,max=0;
int find(int x)
{
int j,k,r=x;
while(r!=a[r])
r=a[r];
k=x;
while(k!=r)
{
j=a[k];
a[k]=r;
k=j;
}
return r;
}
void init()
{
int i;
scanf("%d %d\n",&n,&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d\n",&x[i],&y[i],&w[i]);
}
for(i=1;i<=n;i++)
{
a[i]=i;
}
}
void sort(int i,int j)
{
if(i>=j)
return;
int p,q,t,k;
k=w[(i+j)/2];
p=i;q=j;
while(p<=q)
{
while(w[p]<k)
p++;
while(w[q]>k)
q--;
if(p<=q)
{
t=w[p];
w[p]=w[q];
w[q]=t;
t=x[p];
x[p]=x[q];
x[q]=t;
t=y[p];
y[p]=y[q];
y[q]=t;
p++;q--;
}
}
sort(i,q);
sort(p,j);
}
void kruskal()
{
int i,fx,fy;
for(i=1;i<=m;i++)
{
fx=find(x[i]);
fy=find(y[i]);
if(fx!=fy)
{
a[fx]=fy;
max=w[i];
p++;
if(p==n-1)
return;
}
}
return;
}
int main()
{
freopen("city.in","r",stdin);
freopen("city.out","w",stdout);
init();
sort(1,m);
kruskal();
printf("%d %d ",p,max);
return 0;
}