有向图的最小树形图（朱刘算法）

算法）"/>

有向图的最小树形图（朱刘算法）

最小树形图的定义：

设G=(V,E)是一个有向图，如果具有下述性质：

(1)G中不包含有向环

(2)存在一个顶点vi，它不是任何弧的终点，而V的其他顶点都恰好是唯一的一条弧的终点，则称G是以vi为根的树形图。

最小树形图就是有向图G=(V,E)中以vi为根的树形图中权值和最小的那个。显而易见，对于不同的vi，得到的最小树形图是不一样的，甚至有可能不存在。

1.基本算法

使用的是朱刘算法（Edmonds朱永津和刘振宏在1965年发表的）。下面都指定为根的顶点是v0

最小树形图基于贪心和缩点的思想。所谓缩点，就是将几个点看成是一个点，所有连到这几个点的边都视为连到收缩点，所有从这几个点连出的边都视为从收缩点连出。

(1)求最短弧集

从所有以vi(i≠0)为终点的弧中取一条最短的，若对于点vi，没有入边，则不存在最小树形图，算法结束；如果能取，则得到由n-1个点和n-1条边组成的图G的一个子图G'，该子图的权值一定是最小的，但是不一定是一棵树。

(2)检查E0

若E0没有有向环且不含收缩点，则计算结束，E0就是G的以v0为根的最小树形图。若E0没有有向环，但含收缩点，则转步骤(4)，若E0含有有向环C，则转入步骤(3)。

(3)把G中的C收缩成点u，对于图G中两端都属于C的边都被收缩掉了，其他弧仍保留，得到一个新的图G1，G1中以收缩点为终点的弧的长度要变化，变化的规律是：设点v在环C中，且环中指向v的边长为w，点v'不在环C中，则对于每一条边<v',v>，在G1中有边<v',u>与其对应，且权值WG1(<v',u>)=WG(<v',v>)-W。对于图G中以环C为起点的边<v',v>，在图G1中有边<u,v'>，则WG1(<u,v'>)=WG(<v,v'>)。需要注意的是，在此步生成的图G1中可能存在重边

对于图G和G1

1)如果图G1中没有以v0为根的最小树形图，则图G中也没有

2)如果图G1中有以v0为根的最小树形图，则可以按照步骤(4)中的展开方法得到图G中的最小树形图。

因此，此时需要将G1代入步骤(1)作为图G继续进行计算，反复计算直到图G1的最小树形图求出。

(4)展开收缩点

如果图G1的最小树形图T1已经求出，那么所有T1中的弧都属于T。将图G1的一个收缩点u展开成环C，从C中去掉与T1中弧有相同终点的弧，其他弧都属于T。

总结：求一个图G0的最小树形图，先求出最短弧集合E0。若E0不存在，则图G0的最小树形图不存在。若E0存在且不含有有向环，则E0就是T0中所有的边。如果E0存在且含有有向环，则收缩有向环成一个点u，并形成图G1，继续求G1的最小树形图直到图Gi，若图Gi无最小树形图，则图G0也不存在最小树形图，若图Gi有最小树形图Ti，则逐层展开得到T0.

在计算的过程中可以发现，图Gi与图Gi-1的最小树形图的权值差正好是被缩掉的环的权值和，在这条性质的影响下，如果不需要直到最终的T0中到底有哪几条边，只需知道T0的权值时，可以不需要展开。

时间复杂度分析：对于最小树形图的算法，最多会进行n-2次缩点，每次缩点以及边权修改的时间复杂度为O(n^2)，所以，最小树形图的时间复杂度为O(n^3)。

对应例题:传送门

题解：跟据题目要求建图，然后就是朱刘算法的板子了

附上代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>using namespace std;const int inf=0x3f3f3f3f;
const int maxn=1005;struct point{double x,y;
};
point p[maxn];double dis(point a,point b)
{return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}struct node{int u,v;double len;
};
node edge[maxn*maxn];int pre[maxn],id[maxn],vis[maxn];
double in[maxn];double dir_mst(int root,int n,int m)
{double ans=0;while(1){for(int i=0;i<n;i++){in[i]=inf;}//找最短弧集for(int i=0;i<m;i++){int u=edge[i].u,v=edge[i].v;if(edge[i].len<in[v]&&u!=v){pre[v]=u;in[v]=edge[i].len;}}for(int i=0;i<n;i++){if(i==root){continue;}if(in[i]==inf){//如果某点入度为0，必定找不到return -1;}}//id为环的序号memset(id,-1,sizeof(id));memset(vis,-1,sizeof(vis));in[root]=0;int cnt=0;//找环for(int i=0;i<n;i++){ans+=in[i];int v=i;while(vis[v]!=i&&id[v]==-1&&v!=root){vis[v]=i;v=pre[v];}if(v!=root&&id[v]==-1){for(int u=pre[v];u!=v;u=pre[u]){id[u]=cnt;}id[v]=cnt++;}}if(cnt==0){break;}for(int i=0;i<n;i++){if(id[i]==-1){id[i]=cnt++;}}//建立新图for(int i=0;i<m;i++){int u=edge[i].u,v=edge[i].v;edge[i].u=id[u];edge[i].v=id[v];if(id[u]!=id[v]){edge[i].len-=in[v];}}n=cnt;root=id[root];}return ans;
}int main()
{int n,m;while(~scanf("%d%d",&n,&m)){for(int i=0;i<n;i++){scanf("%lf%lf",&p[i].x,&p[i].y);}for(int i=0;i<m;i++){scanf("%d%d",&edge[i].u,&edge[i].v);--edge[i].u;--edge[i].v;if(edge[i].u!=edge[i].v){edge[i].len=dis(p[edge[i].u],p[edge[i].v]);}else{edge[i].len=inf;}}double ans=dir_mst(0,n,m);if(ans==-1){printf("poor snoopy\n");}else{printf("%.2f\n",ans);}}return 0;
}