1004: 惠民工程

使用kruskal写最小生成树

#include <bits/stdc++.h>
using namespace std;
const int M=105;
const int N=5005;
struct node{int s;int t;int w;bool operator<(const node& a)const{return w>a.w;    //小根堆 }
};int fa[M];
int find(int i){if(fa[i]==i){return i;}else fa[i]=find(fa[i]);return  fa[i];
}
int m,n;
int n2;
int main(){while(scanf("%d%d",&m,&n2)!=EOF){		//m个城市，n个管道 priority_queue<node> que;memset(fa,0,sizeof(fa));if(n2>m*(m-1)/2){n=m*(m-1)/2;}		else n=n2;				//题目给的n2管道数可能很多 for(int i=1;i<=n;i++){int s,t,w;scanf("%d%d%d",&s,&t,&w);que.push({s,t,w});fa[s]=s;fa[t]=t;}if(n<n2){for(int i=n+1;i<=n2;i++){int s,t,w;scanf("%d%d%d",&s,&t,&w);}}int cnt=0;long long sum=0;while(cnt<=m-1&&!que.empty()){node now=que.top();que.pop();if(find(now.s)!=find(now.t)){fa[fa[now.s]]=fa[now.t];cnt++;sum=sum+now.w;}}if(cnt==m-1){printf("%lld\n",sum);}else printf("?\n");}return 0;
}