小黑书上说朱刘算法求的是不定根最小树形图，但是网上找到的资料都说是定根最小树形图……管他呢……

前前后后写了六个小时左右……一开始写每次消掉一个环的DFS，各种2B错误，调了三个小时才好……

然后又改成BFS+拓扑排序的一次消去所有环的方法……这样可以不用记录最小入边的反向边。然后边减小的量用个数组保存起来，这样就不用记录整张图的反向边了。

整个算法的瓶颈在于取最小入边……时间复杂度O(NM)。自己感觉应该不会太慢……不过还是很难写的啊！关于最小树形图的东西有很多论文神马的，小黑书上也写的还算详细，这里就不详细讲了！

总体步骤是：

0.从根开始BFS查看是否所有点都可遍历到。

1.找除根外的点的最小入边。O(m)

2.拓扑排序找环，如果没有环则输出当前最小入边权值和+环的总权值。O(n)

3.用并查集将环缩成一个点（环上所有点的相关边都要连到这个点上）。环的总权值加上这个环的边权和。对于最小入边权为w的点，将其所有入边权值减去w。可以用O(m)的写法，也可以存进数组让其在步骤1中调整O(n)。

4.转步骤1。每次至少减少一个点，步骤1～3最多执行n次。

35行代码，就算不恶意缩行也很短，大概是别人代码量的1/3……不过谁来告诉我为毛BZOJ2260会PE啊！！而且除了ROOT以外还有人AC的！！（虽然真的有好多人PE啊……）

#include <stdio.h>
#include <string.h>
#define maxn 100
#define maxm 10000
int n,nn,m,r,ans,re,f[maxn],que[maxn],bq=-1,eq=1,v[maxn],d[maxn];
struct edge{struct edge *next;int x,t,y;}*map[maxn],*min[maxn],*tail[maxn],st[maxm],*stp=st,*p;
inline getint(){
	int re=0,ch=getchar(),k;
	while(ch!='-'&&(ch<'0'||ch>'9'))if((ch=getchar())<=0)return -1;
	for(k=ch=='-'&&(ch=getchar());ch>='0'&&ch<='9';ch=getchar())re=re*10+ch-48;
	return k?-re:re;
}inline void ADDEDGE(x,y,t){
	if(!tail[x])tail[x]=stp;
	stp->next=map[stp->y=y,stp->x=x];
	(map[x]=stp++)->t=t;
}inline fa(x){
	int y=f[x],r=f[x];
	while(r!=f[r])r=f[r];
	while((f[x]=r)!=(x=y))y=f[y];
	return r;
}main(){
	int i,x,y;
	for(nn=(n=getint())-1,m=getint(),r=0;m--;ADDEDGE(x,y,getint()))x=getint()-1,y=getint()-1;
	for(v[que[0]=r]=1;++bq!=eq;)for(p=map[que[bq]];p;p=p->next)if(!v[p->y])v[que[eq++]=p->y]=1;
	for(i=-1;++i!=n;v[f[i]=i]=0)if(!v[i])return puts("impossible"),0;
	while(bq=i=-1){
		for(p=st-1;++p!=stp;)if(p->y!=r&&(p->x=fa(p->x))!=fa(p->y)){
			if(p->t-=d[p->y],min[p->y=f[p->y]]&&min[p->y]->t>p->t)v[min[p->y]->x]--;
			if(!min[p->y]||min[p->y]->t>p->t)v[p->x]++,min[p->y]=p;
		}for(re=eq=0;++i!=n;d[i]=0,min[i]&&(re+=min[i]->t))if(i!=r&&f[i]==i&&!v[i])que[eq++]=i;
		while(++bq!=eq)if(min[que[bq]]->x!=r&&!--v[min[que[bq]]->x])que[eq++]=min[que[bq]]->x;
		if(eq==nn)return printf("%d\n",ans+re),0;
		for(i=-1;++i!=n;min[i]=0)if(i!=r&&f[i]==i&&v[i])for(p=min[i];v[(p=min[p->x])->y]--;ans+=d[p->y]=min[p->y]->t)if(p->y!=i)tail[f[p->y]=i]->next=map[p->y],tail[i]=tail[p->y],nn--;
	}
}

• inline
• block