题解 P2330 【[SCOI2005]繁忙的都市】

### 一道典型的最小生成树 其实你把模板的代码复制粘贴，再稍微改改就AC了 话不多说，直接上代码： ```cpp #include<cstdio> #include<algorithm> using namespace std; int f[301]; int find(int k){//并查集 if(f[k]==k)return k; return f[k]=find(f[k]); } struct node{ int a,b,val; }; int cmp(node &A,node &B){//kruskal的灵魂 return A.val<B.val; } inline int read(){//快读 char p=0;int r=0,o=0; for(;p<'0'||p>'9';o|=p=='-',p=getchar()); for(;p>='0'&&p<='9';r=(r<<1)+(r<<3)+(p^48),p=getchar()); return o?(~r)+1:r; } node qwq[100001]; int n,m; int ans; int big; int main(){ n=read(); m=read(); for(int i=1;i<=300;i++)f[i]=i; for(int i=1;i<=m;i++){ qwq[i].a=read(); qwq[i].b=read(); qwq[i].val=read(); } sort(qwq+1,qwq+m+1,cmp);//核心代码（huaji for(int i=1;i<=m;i++){ if(find(qwq[i].a)!=find(qwq[i].b)){ int tmp=qwq[i].val; ans++; f[find(qwq[i].a)]=f[qwq[i].b]; if(big<tmp)big=tmp; } } printf("%d %d",ans,big); return 0; } ```