最小树形图

简介：

在一个有向图中构造一颗最小生成树
(有根树)

解法：

朱刘算法：

1. 判断图的连通性：如果所有点不联通，无解
2. 除根节点外寻找每个点的最小入边，记pre[v]为点v的入边顶点,in[v]为最小入边的边权
3. 判断是否图中是否存在环，如果无环则ans += in[v],输出答案，否则进行4
4. 缩点：将成环的点v\(_1\),v\(_2\),v\(_3\),....,v\(_n\)缩为一个点，ans +=in[v\(_1\)~v\(_n\)]
   更新环外的点到环的距离：w -= in[v]

不断重复3,4直到没有环输出ans，算法复杂度O(n*m)

借用别人的图来解释一下缩点：

在第2步出现了环2-3-4，ans += in[2-3-4],之后更新点1到环的距离，因为对于同一个点，只有一个最小入边，此时对于点4最小入边存在两个（1,3），而边3-4已经加入到了ans之中，所以对于边1-4要消去这个影响，故而此时边1-4的边权变为了(4-2 =)2,减去的2就是边3-4的影响，我们可以理解为此时我们断开了边3-4，连上了边1-4【依据：除根节点外，每个节点都有且只有一个最小入边】

代码实现：

例：UVA-11183
P4716 【模板】最小树形图

#include<iostream>
# include<cmath>
# include<cstring>
# include<algorithm>
using namespace std;
# define int long long
# define endl "\n"
const int N = 1e3 + 10, M = 4e4 + 10, inf = 0x3f3f3f3f;
int n, m;
struct edg {
	int a, b;
	int w;
} e[M];
int in[N];//最小入边 
int pre[N];//最小入边前驱 
int id[N], vis[N];//id:缩点后的编号 
int root = 1;//根 
int ans = 0;//答案 
int getans() {

	int cnt = 0, u, v;
	int laz;
	while (1) {
		/*初始化所有最小入边为inf*/ 
		for (int i = 1; i <= n; ++i) {
			in[i] = inf;
			id[i] = vis[i] = 0;
		}
		//1.寻找除根节点外所有点的最小入边 
		for (int i = 1; i <= m; ++i) {
			/*如果a,b不同并且当前边权小于点b的最小入边则更新*/
			if (e[i].a ^ e[i].b && e[i].w < in[e[i].b]) {
				pre[e[i].b] = e[i].a;
				in[e[i].b] = e[i].w;
			}
		}
		in[root] = 0;
		for (int i = 1; i <= n; ++i) {
			//2.判断连通性，如果某个点的最小入边为inf则说明其无入边，不联通 
			if (in[i] == inf) return (ans = -1);
			ans += in[i];
			u = i;
			//3.判断是否成环 
			while (u ^ root && vis[u]^i && !id[u]) {
				//若当前节点不为根并且非入点(非环)并且尚未编号就不断向前遍历 
				vis[u] = i;
				u = pre[u];
			}
			/*如果当前节点不为根节点并且没有编号，说明成环*/ 
			if (u ^ root && !id[u]) {
				/*缩点*/ 
				id[u] = ++cnt;
				for (v = pre[u]; v ^ u; v = pre[v]) {
					id[v] = cnt;
				}
			}
		}
		/*如果没有缩点说明无环返回ans*/ 
		if (!cnt) return ans;
		//更新所有节点编号 
		for (int i = 1; i <= n; ++i) {
			if (!id[i]) id[i] = ++cnt;
		}
		//4.更新环外点到环的距离 
		for (int i = 1; i <= m; ++i) {
			laz = in[e[i].b];//最小入边 
			/*如果a,b不属于同一个id说明a,b不为同一个环则更新距离*/ 
			if ((e[i].a = id[e[i].a]) != (e[i].b = id[e[i].b])) {
				e[i].w -= laz;
			}
		}
		n = cnt;//更新节点数目(缩点后) 
		root = id[root];//更新根节点 
		cnt = 0;
	}
}
int ll = 0;
void solve() {
	ll++;
	cin >> n >> m;
	ans = 0;
	root = 1;
	for (int i = 1; i <= m; ++i) {
		int a, b, w;
		cin >> a >> b >> w;
		e[i] = {a + 1, b + 1, w};
	}
	getans();//朱刘算法 
	printf("Case #%d: ", ll);
	if (ans != -1) printf("%d\n", ans);
	else printf("Possums!\n");


}
int tt;
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	tt = 1;
	cin >> tt;
	while (tt--) solve();


	return 0;
}