首页 > 代码库 > Bzoj1083 1083: [SCOI2005]繁忙的都市【MST】
Bzoj1083 1083: [SCOI2005]繁忙的都市【MST】
大水题,真不知道出题者是怎么把这么水的题出的这么长的TAT 其实这题在于考语文水平,一共三个要求,前两个要求意思就是要选出的道路是树形的,最后一个要求就是要权值最小,于是整个题意说白了就是求一棵MST,以前向星的形式给出最容易想到kruskal算法,于是这题顺利结束,从看题一直到调试结束半个小时搞定……
#include<iostream>
#include<cstdio>
#include <math.h>
using namespace std;
intfather[4000]={0},a[5000]={0},b[5000]={0},v[5000]={0};
void qsort(int l,int r)
{
int mid=v[(l+r)>>1],i=l,j=r,temp;
while (i<j)
{
while (v[i]<mid)i++;
while (v[j]>mid)j--;
if (i<=j)
{
temp=a[i];a[i]=a[j];a[j]=temp;
temp=b[i];b[i]=b[j];b[j]=temp;
temp=v[i];v[i]=v[j];v[j]=temp;
i++;j--;
}
}
if (i<r)qsort(i,r);
if (l<j)qsort(l,j);
}
int find(int k)
{
if(father[k]==k)return k;else return father[k]=find(father[k]);
}
int main()
{
int n,m,t=0,ans;
scanf("%d%d",&n,&m);
for (inti=1;i<=m;i++)scanf("%d%d%d",&a[i],&b[i],&v[i]);
for (int i=1;i<=n;i++)father[i]=i;
qsort(1,m);
for (int i=1;i<=m;i++)
{
if (find(a[i])!=find(b[i]))
{
father[find(a[i])]=father[find(b[i])];//合并
t++;
if (t==n-1)ans=v[i];
}
}
printf("%d %d\n",t,ans);
return 0;
}
Bzoj1083 1083: [SCOI2005]繁忙的都市【MST】