解题思路:
注意事项:
参考代码:
#include<iostream> #include<algorithm> using namespace std; const int N=110,M=1e6+10; int p[N]; struct Edge { int a,b,w,r; }q[M]; int find(int x) { if(x!=p[x]) p[x]=find(p[x]); return p[x]; } bool cmp(Edge a,Edge b) { return a.w<b.w; } int main() { int n,m; cin>>n; while(n) { m=n*(n-1)/2; for(int i=1;i<=n;i++) p[i]=i; int cont=0,ans=n-1,cost=0; for(int j=0;j<m;j++) { int a,b,w,r; cin>>a>>b>>w>>r; if(r==1) { if(find(a)!=find(b)) { p[find(a)]=find(b); ans--; } } else { q[cont].a=a; q[cont].b=b; q[cont].w=w; q[cont].r=r; cont++; } } if(ans==0) cout<<0<<endl; else { sort(q,q+cont,cmp); for(int i=0;i<cont;i++) { int a=find(q[i].a),b=find(q[i].b); if(a!=b) { cost+=q[i].w; p[a]=b; } } cout<<cost<<endl; } cin>>n; } return 0; }
0.0分
0 人评分
蓝桥杯历届试题-九宫重排 (C++代码)浏览:2783 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:742 |
C语言程序设计教程(第三版)课后习题6.5 (C语言代码)浏览:748 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:517 |
淘淘的名单 (C语言代码)浏览:1090 |
C语言程序设计教程(第三版)课后习题6.9 (C语言代码)浏览:627 |
幸运数 (C++代码)浏览:1258 |
1014题解浏览:484 |
C语言程序设计教程(第三版)课后习题9.8 (C语言代码)浏览:608 |
DNA (C语言代码)浏览:735 |