Codeforces 875F Royal Questions (看题解)

我还以为是什么板子题呢。。。

我们把儿子当做点, 公主当做边, 然后就是求边权值最大基环树森林。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long
using namespace std; const int N = 2e5 + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + ;
const double eps = 1e-; int n, m, ans, a[N], b[N], w[N], fa[N], id[N];
bool vis[N]; int getRoot(int x) {
return fa[x] == x ? x : fa[x] = getRoot(fa[x]);
} bool cmp(const int&a, const int& b) {
return w[a] > w[b];
} int main(){
scanf("%d%d", &n, &m);
for(int i = ; i <= m; i++)
scanf("%d%d%d", &a[i], &b[i], &w[i]);
for(int i = ; i <= m; i++) id[i] = i;
for(int i = ; i <= n; i++) fa[i] = i;
sort(id + , id + + m, cmp);
for(int i = ; i <= m; i++) {
int p = id[i];
int x = getRoot(a[p]);
int y = getRoot(b[p]);
if(x != y && (!vis[x] || !vis[y])) {
ans += w[p];
if(!vis[x]) fa[x] = y;
else fa[y] = x;
} else if(!vis[x]){
ans += w[p];
vis[x] = true;
}
}
printf("%d\n", ans);
return ;
}
/*
*/
上一篇:掌握Spark机器学习库-07.14-保序回归算法实现房价预测


下一篇:Android项目架构之业务组件化