Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1031 Accepted Submission(s): 450
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<queue> 7 #include<map> 8 #include<set> 9 #include<vector> 10 #include<cstdlib> 11 #include<string> 12 #define eps 0.000000001 13 typedef long long ll; 14 typedef unsigned long long LL; 15 using namespace std; 16 const int N=200000+100; 17 int parent[N]; 18 int ans; 19 int m,n; 20 struct node{ 21 int u,v,w; 22 }a[N]; 23 bool cmp(node x,node y){ 24 return x.w<y.w; 25 } 26 void init(){ 27 for(int i=0;i<=N;i++)parent[i]=i; 28 } 29 int find(int x){ 30 int r=x; 31 while(parent[r]!=r)r=parent[r]; 32 int i=x; 33 int j; 34 while(i!=r){ 35 j=parent[i]; 36 parent[i]=r; 37 i=j; 38 } 39 return r; 40 } 41 void kruskal(){ 42 for(int i=0;i<m;i++){ 43 int x=find(a[i].u); 44 int y=find(a[i].v); 45 if(x!=y){ 46 parent[x]=y; 47 ans=ans+a[i].w; 48 } 49 } 50 } 51 int main(){ 52 while(scanf("%d%d",&n,&m)!=EOF){ 53 init(); 54 if(m==0&&n==0)break; 55 int sum=0; 56 ans=0; 57 for(int i=0;i<m;i++){ 58 scanf("%d%d%d",&a[i].u,&a[i].v,&a[i].w); 59 sum=sum+a[i].w; 60 } 61 //cout<<sum<<endl; 62 sort(a,a+m,cmp); 63 kruskal(); 64 65 //cout<<ans<<endl; 66 printf("%d\n",sum-ans); 67 } 68 }
原文:http://www.cnblogs.com/Aa1039510121/p/6444074.html