bzoj1083

题解:

简单最小生成树

代码:

#include<bits/stdc++.h>
using namespace std;
#define y1 ____y1
const int N=;
int z[N],f[N],x[N],y[N],n,m,fa[N];
int find(int x)
{
if (x==fa[x])return x;
fa[x]=find(fa[x]);
return fa[x];
}
int cmp(int x,int y)
{
return z[x]<z[y];
}
int main()
{
scanf("%d%d",&n,&m);
for (int i=;i<=m;i++)
{
scanf("%d%d%d",&x[i],&y[i],&z[i]);
f[i]=i;
}
for (int i=;i<=n;i++)fa[i]=i;
sort(f+,f+m+,cmp);
int tot=,ans=;
for (int i=;i<=m;i++)
{
int x1=find(x[f[i]]),y1=find(y[f[i]]);
if (x1!=y1)
{
fa[x1]=fa[y1];
tot++;
ans=z[f[i]];
}
}
printf("%d %d",tot,ans);
}
上一篇:np.tile语法


下一篇:python编码(二)