P4176 最小树形图

#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#include <set>
#include <map>

using namespace std;
#define ll long long
#define mem(a, b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
#define DBG printf("this is a input\n")
#define fi first
#define se second
#define mk(a, b) make_pair(a,b)
#define p_queue priority_queue

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
struct e
{
    int f ,t ,w;
}edge[10005];
int n , m , r;
int in[10005], id[10005], vis[10005], pre[10005];
int solve(int root, int V , int E)
{
    int ans = 0;
    while(true) {
        for (int i = 1; i <= V; i++)
            in[i] = INF;
        //寻找最小边
        for (int i = 1; i <= E; i++) {
            int u = edge[i].f, v = edge[i].t, w = edge[i].w;
            if (w < in[v] && u != v) {
                pre[v] = u;
                in[v] = w;
            }
        }
        //判断是否存在孤立节点
        for (int i = 1; i <= V; i++) {
            if (i != root && in[i] == INF)
                return -1;
        }
        //判断环
        int cnt = 1;
        mem(id, -1);
        mem(vis, -1);
        in[root] = 0;
        for (int i = 1; i <= V; i++) {
            ans += in[i];
            int v = i;
            while (vis[v] != i && id[v] == -1 && v != root) {
                vis[v] = i;
                v = pre[v];
            }
            //缩点
            if (v != root && id[v] == -1) {
                for (int u = pre[v]; u != v; u = pre[u])
                    id[u] = cnt;
                id[v] = cnt++;
            }
        }
        if (cnt == 1)
            break;
        for (int i = 1; i <= V; i++)
            if (id[i] == -1)
                id[i] = cnt++;
        //建立新图，缩点，重新标记
        for(int i = 1 ; i <= E ; i ++)
        {
            int u = edge[i].f;
            int v = edge[i].t;
            edge[i].f = id[u];
            edge[i].t = id[v];
            if(id[u] != id[v])
                edge[i].w -= in[v];
        }
        V = cnt-1;
        root = id[root];
    }
    return ans;
}
int main(void)
{
    scanf("%d %d %d",&n, &m, &r);
    for(int i = 1 ; i <= m ; i ++)
        scanf("%d %d %d",&edge[i].f,&edge[i].t,&edge[i].w);
    printf("%d",solve(r,n,m));
}