最小树形图

每个点贪心找最小的前驱选上，然后分情况：
如果形成一棵树，那么算法结束；
否则对该图缩点，scc之间的边的权值赋值成 用这条边替代原来终点的前驱的代价 的权值，表示换去一条环边，然后做最小树形图即可。
每轮至少缩去一个点，复杂度 (O(n^2+nm))。

void tarjan(int u)
{
	dfn[u]=low[u]=++ord;
	stk[++top]=u;
	ins[u]=1;
	int v=nxt[u];
	if(!dfn[v])
		tarjan(v),low[u]=min(low[u],low[v]);
	else if(ins[v])
		low[u]=min(low[u],dfn[v]);
	if(dfn[u]==low[u])
	{
		++cnt;
		for(int x=stk[top];;x=stk[top])
		{
			--top;
			scc[x]=cnt;
			ins[x]=0;
			if(x==u)
				break;
		}
	}
}

int work(int n,vector<edge>e,int root)
{
	int ans=0;
	while(1)
	{
		vector<int>d(n+1,1e9);
		for(int i=1; i<=n; i++)
			nxt[i]=scc[i]=dfn[i]=low[i]=ins[i]=0;
		for(auto &k:e)
			if(k.u!=k.v&&k.w<d[k.v])
				d[k.v]=k.w,nxt[k.v]=k.u;
		nxt[root]=root;
		d[root]=0;
		for(int i=1; i<=n; i++)
		{
			if(!nxt[i])
				return -1;
			ans+=d[i];
		}
		top=ord=cnt=0;
		for(int i=1; i<=n; i++)
			if(!dfn[i])
				tarjan(i);
		if(cnt==n)
			break;
		vector<edge> ne;
		for(auto &k:e)
			if(scc[k.u]!=scc[k.v])
				ne.push_back((edge){scc[k.u],scc[k.v],k.w-d[k.v]});
		e=ne; n=cnt; root=scc[root];
	}
	return ans;
}