【总结】最小树形图 朱刘算法

前言

省选复习的时候，发现没写博客。。。

来补一篇。。

最小树形图

就是有向图的最小生成树，满足从根出发，能到达所有节点，且边权和尽可能小。

朱刘算法

很暴力的方法，每个点在指向它的边中，选择最小的一条（根节点不选）。

然后答案加上每个点选出的边权。

然后可能有环，就缩环成点，然后改一下边权

val’-=val，表示之后若选择val’，则必须断开val

一直这样做下去，直到某一次找不到环了就停止。

复杂度$O(N*M)$O(N∗M)

模板题

BZOJ4349

第一次是最小树形图，第二次及以后攻打，就用最小的即可。

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#define SF scanf
#define PF printf
#define INF 0x3FFFFFFF
#define MAXN 60
#define MAXM 2600
using namespace std;
struct Edge{
	int u,v;
	double val;	
	Edge() {}
	Edge(int u1,int v1,double val1):u(u1),v(v1),val(val1) {}
}edge[MAXM];
int num[MAXN],pre[MAXN],id[MAXN],vis[MAXN];
double minv[MAXN],in[MAXN];
int rt,ncnt;
double solve(int n){
	double res=0;
	while(1){
		for(int i=1;i<=n;i++)
			in[i]=INF;
		for(int i=1;i<=ncnt;i++){
			int u=edge[i].u;
			int v=edge[i].v;
			double val=edge[i].val;
			if(in[v]>val){
				in[v]=val;
				pre[v]=u;
			}
		}
		int tot=0;
		memset(id,0,sizeof id);
		memset(vis,0,sizeof vis);
		in[rt]=0;
		for(int i=1;i<=n;i++){
			res+=in[i];
			int v=i;
			while(vis[v]!=i&&id[v]==0&&v!=rt){
				vis[v]=i;
				v=pre[v];	
			}
			if(v!=rt&&id[v]==0){
				id[v]=++tot;
				for(int u=pre[v];u!=v;u=pre[u])
					id[u]=tot;
			}
		}
		if(tot==0)
			break;
		for(int i=1;i<=n;i++)
			if(id[i]==0)
				id[i]=++tot;
		int cnt1=0;
		for(int i=1;i<=ncnt;i++){
			int u=edge[i].u;
			int v=edge[i].v;
			double val=edge[i].val;
			val-=in[v];
			if(id[u]!=id[v])
				edge[++cnt1]=Edge(id[u],id[v],val);
		}
		rt=id[rt];
		n=tot;
		ncnt=cnt1;
	}
	return res;
}
int main(){
	int n,u,v,m;
	double val;
	SF("%d",&n);
	n++;
	rt=n;
	for(int i=1;i<=n-1;i++){
		SF("%lf%d",&val,&num[i]);
		minv[i]=val;
		edge[++ncnt]=Edge(rt,i,val);
	}
	SF("%d",&m);
	for(int i=1;i<=m;i++){
		SF("%d%d%lf",&u,&v,&val);
		minv[v]=min(minv[v],val);
		edge[++ncnt]=Edge(u,v,val);	
	}
	double res=solve(n);
	for(int i=1;i<n;i++)
		res+=(num[i]-1)*minv[i];
	PF("%.2lf",res);
}