最小树形图

算法背景

引入

给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。

显然，Prim 和 Kruskal 任选其一。

正题

现在，我们把无向图改成有向图，那么我们该怎么做呢？

题目：给定包含 $n$ 个结点， $m$ 条有向边的一个图。试求一棵以结点 $r$ 为根的最小树形图，并输出最小树形图每条边的权值之和，如果没有以 $r$ 为根的最小树形图，输出 $−1$。

算法思想

朱刘算法

时间复杂度 $O(nm)$。

我们观察到树上面除了根节点，每一个节点都有一个入边，所以我们选择每一个节点的最小入边为它的树边，但是这样可能形成环，所以我们在形成环时直接缩点，然后接着求解。

DMST

Tarjan 老爷子提出了一种能够在 $O(m+n\log n)$ 时间内解决最小树形图问题的算法（他咋啥都会？）。

现在，我们先假设这张图是强联通的（不是就添加一个环使之强联通），然后进行以下操作：

1. 选择一个节点 $v$（保证 $v$ 不是根节点）
2. 再将 $v$ 的最小入边加入到候选队列中
3. 如果新加入的这条边使队列中的边形成了环，那么将构成环的那些结点收缩为一个新的节点

在操作的结束，我们一定会形成一个巨大的节点，然后我们把它拆开（伸展）：

以原先要求的根节点 $r$ 为起始点，对 $r$ 到收缩树的根上的每一个环进行伸展。再以 $r$ 的祖先结点 $f_r$ 为起始点，将其到根的环展开，循环往复，直到遍历完所有的结点。

那么我们怎么快速实现收缩呢？我们发现我们可以使用可并堆来快速维护一个节点的所有入边。

于是再具体一点吧：

向队列 $P$ 中放入所有的结点（包括合并过后的），并初始选择任意一节点 $a$（不影响答案），只要队列不为空，就进行以下步骤：

1. 选择 $a$ 的最小入边，保证不存在自环，并找到另一头的结点 $b$。如果结点 $b$ 没有被记录过说明未形成环，令 $a\leftarrow b$，继续当前操作寻找环。

2. 如果 $b$ 被记录过了，就说明出现了环。总结点数加一（新建节点），并将环上的所有结点重新编号，对堆进行合并，以及结点总权值的更新。更新权值操作就是将环上所有结点的入边都收集起来，并减去环上入边的边权。

从 OI-Wiki 上偷一张图过来。

左边的强连通图在收缩后就形成了右边的一棵收缩树，其中 $a$ 是结点 $1$ 与结点 $2$ 收缩后的结点，$b$ 是结点 $3$，结点 $4$，结点 $5$ 收缩后的超级结点，$A$ 是两个超级结点 $a$ 与 $b$ 收缩后形成的。

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int N = 100 + 5, inf = 0x3f3f3f3f;
struct mss {
	int fa[N << 1];
	mss() :fa() {}
	int& operator()(int x) { return fa[x]; }
	int operator[](int x) { return fa[x] ? fa[x] = (*this)[fa[x]] : x; }
}id;
struct Edge {
	int u, v, w, val;
};
struct Node {
	Edge* data;
	int dist, add;
	Node* ls, * rs;
	Node(Edge* data) : data(data), dist(1), add(), ls(), rs() {}
	void pushdown() {
		if (ls) ls->add += add;
		if (rs) rs->add += add;
		data->w += add;
		add = 0;
	}
};
Node* merge(Node* x, Node* y) {
	if (!x) return y;
	if (!y) return x;
	if (x->data->w + x->add > y->data->w + y->add) swap(x, y);
	x->pushdown();
	x->rs = merge(x->rs, y);
	if (!x->ls || x->ls->dist < x->rs->dist) swap(x->ls, x->rs);
	if (x->rs) x->dist = x->rs->dist + 1;
	else x->dist = 1;
	return x;
}
Edge* top(Node*& x) {
	Edge* r = x->data;
	x->pushdown();
	x = merge(x->ls, x->rs);
	return r;
}
vector<Edge> in[N];
int n, m, fa[N << 1], nxt[N << 1];
Edge* cyc[N << 1];
Node* pq[N << 1];
bool vis[N << 1];
ll expand(int x, int t) {
	ll r = 0;
	for (; x != t; x = fa[x]) {
		ll sum = 0;
		for (int u = nxt[x]; u != x; u = nxt[u]) {
			if (cyc[u]->val >= inf) return inf;
			ll child = expand(cyc[u]->v, u);
			if (child >= inf || sum >= inf) {
				sum = inf; break;
			}
			sum += child + cyc[u]->val;
		}
		if (sum >= inf || (r += sum) >= inf) return inf;
	}
	return r;
}
int main() {
	int rt;
	cin >> n >> m >> rt;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		in[v].push_back({ u, v, w, w });
	}
	for (int i = 1; i <= n; i++) in[i].push_back({ i > 1 ? i - 1 : n, i, inf, inf });
	for (int i = 1; i <= n; i++) {
		queue<Node*> q;
		for (Edge& e : in[i]) q.push(new Node(&e));
		while (q.size() > 1) {
			Node* u = q.front(); q.pop();
			Node* v = q.front(); q.pop();
			q.push(merge(u, v));
		}
		pq[i] = q.front();
	}
	vis[1] = true;
	for (int a = 1, b = 1; pq[a]; b = a, vis[b] = true) {
		do {
			cyc[a] = top(pq[a]);
			a = id[cyc[a]->u];
		} while (a == b && pq[a]);
		if (a == b) break;
		if (!vis[a]) continue;
		a = b;
		n++;
		while (a != n) {
			id(a) = fa[a] = n;
			if (pq[a]) pq[a]->add -= cyc[a]->w;
			pq[n] = merge(pq[n], pq[a]);
			int p = id[cyc[a]->u];
			nxt[p == n ? b : p] = a;
			a = p;
		}
	}
	ll ans = expand(rt, n);
	cout << (ans >= inf ? -1 : ans) << endl;
	return 0;
}