题意
题目链接
sol
朱刘算法?感觉又是一种神仙贪心算法
大概就是每次贪心的用每个点边权最小的入边更新答案,如果不行的话就缩起来找其他的边
不详细说了,丢走人..
#include<bits/stdc++.h> using namespace std; const int maxn = 1e5 + 10, inf = 1e9 + 10; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, m, r, fa[maxn], mn[maxn], id[maxn], vis[maxn]; struct edge { int u, v, w, nxt; }e[maxn]; int head[maxn], num = 1; inline void addedge(int x, int y, int z) { e[num] = (edge) {x, y, z, head[x]}; head[x] = num++; } int zhuliu() { int ans = 0; while("attack is a pig") { for(int i = 1; i <= n; i++) id[i] = vis[i] = 0, mn[i] = inf; int cnt = 0; for(int i = 1; i <= m; i++) if((e[i].u != e[i].v) && (e[i].w < mn[e[i].v])) mn[e[i].v] = e[i].w, fa[e[i].v] = e[i].u; int x; mn[r] = 0;//tag for(int i = 1; i <= n; i++) { if(mn[i] == inf) return -1; ans += mn[i]; for(x = i; (!id[x]) && x != r && (vis[x] != i); x = fa[x]) vis[x] = i; if(x != r && (!id[x])) { id[x] = ++cnt; for(int t = fa[x]; t != x; t = fa[t]) id[t] = cnt; } } if(!cnt) return ans; for(int i = 1; i <= n; i++) if(!id[i]) id[i] = ++cnt; for(int i = 1; i <= m; i++) { int tmp = mn[e[i].v]; if((e[i].u = id[e[i].u]) != (e[i].v = id[e[i].v])) e[i].w -= tmp; } n = cnt; r = id[r]; } return ans; } int main() { memset(head, -1, sizeof(head)); n = read(); m = read(); r = read(); for(int i = 1; i <= m; i++) { int x = read(), y = read(), z = read(); addedge(x, y, z); } printf("%d", zhuliu()); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/606147.html