CSP-S 模拟 19/10/09

CSP-S 模拟 19/10/09

T1：背包模板 T2：分数规划+单调队列模板 T3：​​​华莱士​​​

题意：选一些边并定下方向，使得每个点入度为 1，问选出来的最小边权和 发现我们可以先把这些边选出来，然后再定方向 我们发现一些性质：一个环只可能出不可能进，也就是我们最后选出来的图环两两之间没有边 脑补一些最后选出来的边的模型，就是基环树，环，它们之间不一定联通 考虑最小生成树一般的贪心 如果当前的两个点不联通，加上 如果当前的两个点联通，但当前连通块还没有环，标记一下并加上，如果有环，显然加上不合法 如果当前两个点不连通但两个点的连通块都有环，显然加上不合法 把环的标记打在并查集的祖先上即可

#include#define N 500050using namespace std;int read(){ int cnt = 0, f = 1; char ch = 0; while(!isdigit(ch)){ ch = getchar(); if(ch == '-') f = -1;} while(isdigit(ch)) cnt = cnt*10 + ch-'0', ch = getchar(); return cnt * f;}typedef long long ll;struct Node{ int u, v, w; }e[N];bool cmp(Node a, Node b){ return a.w < b.w;}int n, m;int fa[N]; bool cir[N];int find(int x){ return x == fa[x] ? x : fa[x] = find(fa[x]);}int main(){ n = read(), m = read(); for(int i = 1; i <= n; i++) fa[i] = i; for(int i = 1; i <= m; i++){ e[i].u = read(); e[i].v = read(); e[i].w = read(); } sort(e + 1, e + m + 1, cmp); int cnt = 0; ll ans = 0; for(int i = 1; i <= m; i++){ int u = e[i].u, v = e[i].v, fx = find(u), fy = find(v); if(fx == fy){ if(cir[fx]) continue; cir[fx] = true; ++cnt; ans += (ll)e[i].w;} else{ if(cir[fx] && cir[fy]) continue; fa[fx] = fy; cir[fy] |= cir[fx]; ++cnt; ans += (ll)e[i].w; } } if(cnt != n){ puts("No"); return 0;} cout << ans; return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。