hdu2121 Ice_cream's world II

給一個(gè)有向圖，求最小樹形圖，并輸出根節(jié)點(diǎn)

\(n\leq10^3,\ m\leq10^4\)

最小樹形圖

---

對于求無根最小樹形圖，可以建一個(gè)虛擬節(jié)點(diǎn)，連向其他所有節(jié)點(diǎn)，權(quán)值為 \(\inf\) ，最后的答案即為 \(ans-\inf\) 。無解當(dāng)且僅當(dāng) \(ans>\inf\times2\)

至于求根節(jié)點(diǎn)，可以考慮記下前驅(qū)為虛擬節(jié)點(diǎn)的節(jié)點(diǎn)，但由于節(jié)點(diǎn)編號(hào)不斷改變，因此只需記下連接兩個(gè)節(jié)點(diǎn)的邊即可。

時(shí)間復(fù)雜度 \(O(nm)\)

代碼

#include <bits/stdc++.h> using namespace std;const int maxn = 1010, inf = 2e6; int n, m, tmp, val[maxn], tid[maxn], pre[maxn], vis[maxn]; struct edges {int u, v, w; } e[maxn * 11];void edmonds() {int ans = 0, pos;while (1) {memset(tid, 0, sizeof tid);memset(vis, 0, sizeof vis);for (int i = 1; i < n; i++) {val[i] = 1 << 30;}for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v;if (u != v && e[i].w < val[v]) {val[v] = e[i].w, pre[v] = u;if (u == n) pos = i;}}for (int i = 1; i < n; i++) {if (val[i] > 1e9) {puts("impossible\n"); return;}}int tot = 0;for (int i = 1; i < n; i++) {int u = i;ans += val[i];while (u != n && !tid[u] && vis[u] != i) {vis[u] = i, u = pre[u];}if (u != n && !tid[u]) {tid[u] = ++tot;for (int v = pre[u]; u != v; v = pre[v]) {tid[v] = tot;}}}if (!tot) break;for (int i = 1; i <= n; i++) {if (!tid[i]) tid[i] = ++tot;}for (int i = 1; i <= m; i++) {int u = e[i].u, v = e[i].v;e[i].u = tid[u], e[i].v = tid[v];if (u != v) e[i].w -= val[v];}n = tot;}ans -= inf;if (ans > inf) {puts("impossible\n");} else {printf("%d %d\n\n", ans, pos - m + tmp - 1);} }int main() {while (~scanf("%d %d", &n, &m)) {for (int i = 1; i <= m; i++) {scanf("%d %d %d", &e[i].u, &e[i].v, &e[i].w);e[i].u++, e[i].v++;}for (int i = 1; i <= n; i++) {e[m + i].u = n + 1, e[m + i].v = i, e[m + i].w = inf;}m += (tmp = n), n++;edmonds();}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Juanzhang/p/10388909.html

總結(jié)

以上是生活随笔為你收集整理的hdu2121 Ice_cream's world II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。