题意

Sol

朱刘算法？感觉又是一种神仙贪心算法

大概就是每次贪心的用每个点边权最小的入边更新答案，如果不行的话就缩起来找其他的边

不详细说了，丢走人..

#include
    
     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;}