int g[MAXN][MAXN]; bool remove_tag[MAXN]; // 缩环时删点标记 int fa[MAXN]; // 每轮,每个点的最小前驱节点 bool vis[MAXN]; // 找环的标记
intdirectional_spawning_tree(int root, int n){ int ans = 0; memset(remove_tag, false, sizeof remove_tag); while (true) { // 找每个点的最小前驱边 for (int u = 1; u <= n; u++) { if (remove_tag[u] || u == root) continue; int min_val = INF; int min_node = 0; for (int i = 1; i <= n; i++) { if (remove_tag[i]) continue; if (g[i][u] < min_val) { min_val = g[i][u]; min_node = i; } } // 如果没有前驱,则无解 if (min_node == 0) return-1; fa[u] = min_node; }
// 判断是否有环 bool has_loop = false; int loop_head = 0; for (int i = 1; i <= n; i++) { if (remove_tag[i] || i == root) continue; memset(vis, false, sizeof vis); vis[root] = true; int u = i; while (!vis[u]) { vis[u] = true; u = fa[u]; } if (u != root) { has_loop = true; loop_head = u; break; } }
if (!has_loop) { // 没有环,则算法结束 for (int i = 1; i <= n; i++) { if (remove_tag[i] || i == root) continue; ans += g[fa[i]][i]; } return ans; }
// cout << loop_head << endl;
// 进行缩环操作 // 统计环上的权值 int u = loop_head; do { ans += g[fa[u]][u]; u = fa[u]; } while (u != loop_head);
// 然后处理环上所有入边的权值,入边权值减去环上边的权值 // 这样缩环后再判断找最小前驱边时,选到入环的边就决定了断环的位置 u = loop_head; do { for (int i = 1; i <= n; i++) { if (remove_tag[i]) continue; if (i != fa[u] && g[i][u] != INF) { g[i][u] -= g[fa[u]][u]; } } u = fa[u]; } while (u != loop_head);
// 缩点,转移权值 for (int i = 1; i <= n; i++) { if (remove_tag[i] || i == loop_head) continue; int u = fa[loop_head]; do { g[loop_head][i] = min(g[loop_head][i], g[u][i]); g[i][loop_head] = min(g[i][loop_head], g[i][u]); u = fa[u]; } while (u != loop_head); }
// 把环上其他的点都标记删除 u = fa[loop_head]; do { remove_tag[u] = true; u = fa[u]; } while (u != loop_head); } }
intmain(){ int n = read(); int m = read(); int r = read(); memset(g, INF, sizeof g); for (int i = 1; i <= m; i++) { int u = read(); int v = read(); int w = read(); g[u][v] = min(g[u][v], w); } int res = directional_spawning_tree(r, n); write(res); }