本文共 2118 字，大约阅读时间需要 7 分钟。
给你n个点，1个点到另一个点连接花费c，但是如果几个点可以相互可达，则这几个点连通花费为0.
求将整个图连通的最小花费。
tarjan，求出强连通子图。
对每个子图的进点的最小值更新，再累加即可，（不过不知道为什么）
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long LL;const int MAXN = 5e4+10;const int INF = 0x3f3f3f3f;struct Node{ int from_, to_, value_; Node(int from, int to, int value):from_(from), to_(to), value_(value){} bool operator < (const Node &that) const { return this->value_ > that.value_; }};vector G[MAXN];stack St;int Dfn[MAXN], Low[MAXN];int Vis[MAXN], Dis[MAXN];int Fa[MAXN], Val[MAXN];int Num[MAXN];int n, m;int times, cnt;void Init(){ for (int i = 1;i <= n;i++) G[i].clear(), Fa[i] = i; memset(Dfn, 0, sizeof(Dfn)); memset(Low, 0, sizeof(Low)); memset(Vis, 0, sizeof(Vis)); memset(Dis, 0, sizeof(Dis)); memset(Num, 0, sizeof(Num)); memset(Val, 0, sizeof(Val)); times = cnt = 0;}void Tarjan(int x){ Dfn[x] = Low[x] = ++times; Vis[x] = 1; St.push(x); for (int i = 0;i < G[x].size();i++) { int node = G[x][i].to_; if (Dfn[node] == 0) { Tarjan(node); Low[x] = min(Low[x], Low[node]); } else if (Vis[node] == 1) Low[x] = min(Low[x], Dfn[node]); } if (Low[x] == Dfn[x]) { cnt++; Num[cnt] = 0; while (St.top() != x) { Num[cnt]++; Fa[St.top()] = cnt; Vis[St.top()] = 0; St.pop(); } Num[cnt]++; Fa[St.top()] = cnt; Vis[St.top()] = 0; St.pop(); }}int main(){ int t, cn = 0; while (~scanf("%d%d", &n, &m)) { Init(); int l, r, v; for (int i = 1;i <= m;i++) { scanf("%d%d%d", &l, &r, &v); l++, r++; G[l].emplace_back(l, r, v); } for (int i = 1;i <= n;++i) if (!Dfn[i]) Tarjan(i); for (int i = 1;i <= cnt;i++) Val[i] = INF; for (int i = 1;i <= n;i++) { for (int j = 0;j < G[i].size();j++) { int node = G[i][j].to_; if (Fa[i] != Fa[node]) Val[Fa[node]] = min(Val[Fa[node]], G[i][j].value_); } } int res = 0; for (int i = 1;i <= cnt;i++) if (Val[i] != INF) res += Val[i]; cout << res << endl; } return 0;}
转载于:https://www.cnblogs.com/YDDDD/p/10822851.html