这是一道模板题。
给定包含 nn 个结点， mm 条有向边的一个图。试求一棵以结点 rr 为根的最小树形图，并输出最小树形图每条边的权值之和，如果没有以 rr 为根的最小树形图，输出 -1−1。
第一行包含三个整数 n,m,rn,m,r，意义同题目所述。
接下来 mm 行，每行包含三个整数 u,v,wu,v,w，表示图中存在一条从 uu 指向 vv 的权值为 ww 的有向边。
如果原图中存在以 rr 为根的最小树形图，就输出最小树形图每条边的权值之和，否则输出 -1−1。
输入
4 6 1 1 2 3 1 3 1 4 1 2 4 2 2 3 2 1 3 4 1输出
3输入
4 6 3 1 2 3 1 3 1 4 1 2 4 2 2 3 2 1 3 4 1输出
4输入
4 6 2 1 2 3 1 3 1 4 1 2 4 2 2 3 2 1 3 4 1输出
-1样例 11 解释
最小树形图中包含第 22， 55， 66 三条边，总权值为 1 + 1 + 1 = 31+1+1=3
样例 22 解释
最小树形图中包含第 33， 55， 66 三条边，总权值为 2 + 1 + 1 = 42+1+1=4
样例 33 解释
无法构成最小树形图，故输出 -1−1 。
数据范围
对于所有数据，1 \leq u, v \leq n \leq 1001≤u,v≤n≤100, 1 \leq m \leq 10^41≤m≤104, 1 \leq w \leq 10^61≤w≤106。
kuangbin模板：
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int inf = 0x3f3f3f3f; const int N = 110; const int M = 2e4 + 10; struct Edge { int u, v, cost; }edge[N]; int g[N][N], pre[N], id[N], vis[N], in[N]; int zhuliu(int root, int n, int m) { int res = 0, u, v; while(1) { for(int i = 0; i < n; ++i) in[i] = inf; for(int i = 0; i < m; ++i) { if(edge[i].u != edge[i].v && edge[i].cost < in[edge[i].v]) { pre[edge[i].v] = edge[i].u; in[edge[i].v] = edge[i].cost; } } for(int i = 0; i < n; ++i) if(i != root && in[i] == inf) return -1; int tn = 0; memset(id, -1, sizeof(id)); memset(vis, -1, sizeof(vis)); in[root] = 0; for(int i = 0; i < n; ++i) { res += in[i]; 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] = tn; id[v] = tn++; } } if(tn == 0) break; for(int i = 0; i < n; ++i) if(id[i] == -1) id[i] = tn++; for(int i = 0; i < m; ) { v = edge[i].v; edge[i].u = id[edge[i].u]; edge[i].v = id[edge[i].v]; if(edge[i].u != edge[i].v) edge[i++].cost -= in[v]; else swap(edge[i], edge[--m]); } n = tn; root = id[root]; } return res; } int main() { int n, m, root; scanf("%d%d%d", &n, &m, &root); for(int i = 0; i < n; ++i) for(int j = 0; j < n; ++j) g[i][j] = inf; int u, v, w; while(m--) { scanf("%d%d%d", &u, &v, &w); if(u == v) continue; g[u - 1][v - 1] = min(g[u - 1][v - 1], w); } int tot = 0; for(int i = 0; i < n; ++i) { for(int j = 0; j < n; ++j) { if(g[i][j] < inf) { edge[tot].u = i; edge[tot].v = j; edge[tot++].cost = g[i][j]; } } } int ans = zhuliu(root - 1, n, tot); if(ans == -1) printf("-1\n"); else printf("%d\n", ans); return 0; }
