解题思路:
继续并查集+快排
#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 人评分
printf基础练习2 (C语言代码)浏览:3363 |
【蟠桃记】 (C语言代码)浏览:2219 |
C二级辅导-温度转换 (C语言代码)浏览:2321 |
C二级辅导-统计字符 (C语言代码)浏览:729 |
C语言考试练习题_保留字母 (C语言代码)浏览:685 |
矩形面积交 (C语言代码)浏览:1511 |
不知道哪里错了浏览:1141 |
C语言程序设计教程(第三版)课后习题7.4 (Java代码)浏览:839 |
C语言程序设计教程(第三版)课后习题6.1 (C语言代码)浏览:450 |
【明明的随机数】 (C++代码)浏览:779 |