本题的 $\mathcal{O}(nm)$ 做法有一种常见错误实现。

以 YellowBean_Elsa 的代码为例：

inline bool solve(){
	while(1){
		init();
		fu(i,1,m)//寻找最小入边 
			if(u[i]!=v[i] && w[i]<mn[v[i]])
				mn[v[i]]=w[i],fa[v[i]]=u[i];
		fu(i,1,n)if(mn[i]==inf)return 0;//有点莫得入边，死也构不成树 
		fu(i,1,n){
			ans+=mn[i];
			int x; 
			//从i点沿着挑出来的边走，注意不要侵扰到别的环或跑到根去 
			for(x=i;x!=rt && top[x]!=i && !scc[x];x=fa[x])top[x]=i;
			if(x!=rt && !scc[x]){//top[x]=i, 即跑了一圈回到了 x
				scc[x]=(++cnt);
				for(int y=fa[x];y!=x;y=fa[y])scc[y]=cnt;
			}
		}if(!cnt)return 1;//莫得环了，弄到了最小树形图 
		fu(i,1,n)if(!scc[i])scc[i]=(++cnt);//必要操作，否则缩点后点数与根会受影响 
		fu(i,1,m){
			int x=u[i],y=v[i];
			u[i]=scc[x],v[i]=scc[y];//缩点 
			if(scc[x]!=scc[y])w[i]-=mn[y];//修改边权 
		}n=cnt,rt=scc[rt];
	}
}

找环的过程中用起点标记是否访问过，for(x=i;x!=rt && top[x]!=i && !scc[x];x=fa[x])top[x]=i;，不直接使用 bool 标记的原因是对于包含根的环，可能由于之前的标记，最后错误地把根缩进了环里。

以样例为例，如图，红边是每个点选出的入边，当找环的循环遍历到点 4 时，由于点 3 已经遍历过，会在 $x=3$ 时终止，然后从 $3$ 开始，将 $1,3,4$ 缩成环。

但是用起点标记时间复杂度是错的，可以卡成 $\mathcal{O}(n(n^2+m))$。

只要将删点次数卡满，每次再让每个点跳的次数卡满就行，具体来说，可以将以下的图延伸到 $n=3000$。

数据生成器：

int n = 3000 , m = (n - 1) * 2 , rt = n;
cout << n << ' ' << m << ' ' << rt << "\n";
for(int i = 1 ; i < n ; i++)
{
	cout << i << ' ' << i + 1 << ' ' << i << "\n";
	cout << i + 1 << ' ' << i << ' ' << i + 1 << "\n";
}

令人震惊的是，题解区所有题解的 $\mathcal{O}(nm)$ 实现，都采用了这种写法，导致时间复杂度错误，仅在本题的数据范围下可以通过。

但事实上，只需要进行很小的改动：遇到标记过的点就退出，只有当前点成环才缩环。即可保证时间复杂度为严格 $\mathcal{O}(nm)$。

for(x=i;x!=rt && !top[x] && !scc[x];x=fa[x])top[x]=i;
if(x!=rt && top[x] == i){//top[x]=i, 即跑了一圈回到了 x
    scc[x]=(++cnt);
    for(int y=fa[x];y!=x;y=fa[y])scc[y]=cnt;
}

希望各位引以为戒，仔细分析自己代码的时间复杂度，不要想当然。