解题思路:
继续并查集+快排
#include<bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 7; struct Node { int x, y, t; int flag; }s[MAXN]; int N, M; int f[MAXN]; int getf(int n) { if (f[n] == n) return n; else return getf(f[n]); } bool cmp(Node a,Node b) { if(a.flag == b.flag) return a.t < b.t; return a.flag > b.flag; } int main() { while (~scanf("%d", &N) && N) { M=N * (N - 1) / 2; for (int i = 1; i <= M; i++) scanf("%d%d%d%d", &s[i].x, &s[i].y, &s[i].t, &s[i].flag); for (int i = 1; i <= N; i++) f[i] = i; sort(s + 1, s + 1 + M, cmp); int ans = 0; for (int i = 1; i <= M; i++) { int fx = getf(s[i].x), fy = getf(s[i].y); if (fx != fy) { f[fx] = fy; N--; if(!s[i].flag) ans+=s[i].t; if(N==1) { cout<<ans<<endl; break; } } } } return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题6.8 (C语言代码)浏览:765 |
【计算球体积】 (C语言代码)浏览:1101 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:534 |
母牛的故事 (C语言代码)浏览:715 |
青年歌手大奖赛_评委会打分 (C语言代码)浏览:2142 |
C语言程序设计教程(第三版)课后习题8.5 (C语言代码)浏览:550 |
字符串对比 (C++代码)浏览:556 |
C语言程序设计教程(第三版)课后习题7.2 (C++代码)浏览:430 |
C语言程序设计教程(第三版)课后习题8.4 (C++代码)浏览:448 |
简单的a+b (C语言代码)浏览:657 |