【Bzoj1083】繁忙的都市

惊现SCOI签到题？直接把最小生成树的ans+=改为ans=就行？

代码中一些没用的部分就不要嘲讽了= = 拿的刚学最小生成树时的模板。

#include<cstdio>#include<algorithm>using namespace std;const int maxn = 5000 + 10 ;const int maxm = 200000 + 10;int father[maxn];struct Edge{    int x;    int y;    int w;}a[maxm];int find(int x){    if(father[x]!=x) father[x]=find(father[x]);    return father[x]; }void unionn(int r1,int r2){    if(find(r1)!=find(r2))    father[find(r1)]=find(r2);}int cmp(Edge a,Edge b){    return a.w<b.w;}int main(){    int m,n;    scanf("%d%d",&n,&m);        for(int i=1;i<=m;i++)    scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w);        sort(a+1,a+m+1,cmp);        for(int i=1;i<=n;i++)    father[i]=i;        int ans=0,rp=0;        for(int i=1;i<=m;i++){        if(find(a[i].x)!=find(a[i].y)){            unionn(a[i].x,a[i].y);            ans=a[i].w;            rp++;        }        if(rp==n-1)        break;    }    PRintf("%d %d",n-1,ans);    return 0; }