最小树形图 朱刘算法【转载】

算法【转载】"/>

最小树形图 朱刘算法【转载】

转载： 先保存下来
有固定根的最小树形图求法O(VE)：
首先消除自环，显然自环不在最小树形图中。然后判定是否存在最小树形图，以根为起点DFS一遍即可。
之后进行以下步骤。
设cost为最小树形图总权值。
0.置cost=0。
1.求最短弧集合Ao （一条弧就是一条有向边）
除源点外，为所有其他节点Vi，找到一条以Vi为终点的边，把它加入到集合Ao中。
（加边的方法：所有点到Vi的边中权值最小的边即为该加入的边，记prev[vi]为该边的起点，mincost[vi]为该边的权值）
2.检查Ao中的边是否会形成有向圈，有则到步骤3，无则到步骤4。
（判断方法：利用prev数组，枚举为检查过的点作为搜索的起点，做类似DFS的操作）
3.将有向环缩成一个点。
假设环中的点有（Vk1，Vk2，… ，Vki）总共i个，用缩成的点叫Vk替代，则在压缩后的图中，其他所有不在环中点v到Vk的距离定义如下：
gh[v][Vk]=min { gh[v][Vkj]-mincost[Vkj] } (1<=j<=i)而Vk到v的距离为
gh[Vk][v]=min { gh[Vkj][v] } (1<=j<=i)
同时注意更新prev[v]的值，即if(prev[v]==Vkj) prev[v]=Vk
另外cost=cost+mincost[Vkj] (1<=j<=i)
到步骤1.
4.cost加上Ao的权值和即为最小树形图总权值。
如要输出最小树形图较烦，没实现过。
找环O(V)，收缩O(E)，总复杂度O(VE)。

对于不固定根的最小树形图，wy教主有一巧妙方法。摘录如下：
新加一个点，和每个点连权相同的边，这个权大于原图所有边权的和，这样这个图固定跟的最小树形图和原图不固定跟的最小树形图就是对应的了。
代码：

#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<cmath>  
using namespace std;
#define maxn 120  
#define INF 99999999999.0  
int n, m;
struct node
{double x, y;
}a[maxn];
inline double get_dis(node a, node b)
{double x = a.x - b.x;double y = a.y - b.y;return sqrt(x*x + y*y);
}
double map[maxn][maxn];
bool flag[maxn];
int pre[maxn];
void dfs(int x)
{flag[x] = true;for (int i = 1; i <= n; i++)if (!flag[i] && map[x][i] != INF)dfs(i);
}
bool check()
{memset(flag, 0, sizeof(flag));dfs(1);for (int i = 1; i <= n; i++)if (!flag[i])return false;return true;
}
double solve()
{memset(flag, 0, sizeof(flag));//flag是true的点是被去掉的点  int i, j, k;double ans = 0;while (1){for (i = 2; i <= n; i++)if (!flag[i]){pre[i] = i;map[i][i] = INF;for (j = 1; j <= n; j++)if (!flag[j]){if (map[pre[i]][i]>map[j][i])pre[i] = j;}}for (i = 2; i <= n; i++)if (!flag[i]){bool mark[maxn];memset(mark, 0, sizeof(mark));for (j = i; j != 1 && !mark[j]; mark[j] = true, j = pre[j]);//寻找环，返回在环内的一点（注意从i出发能找到换不代表n在环内）  if (j == 1)continue;i = j;ans += map[pre[i]][i];for (j = pre[i]; j != i; j = pre[j]){ans += map[pre[j]][j];flag[j] = true;}for (j = 1; j <= n; j++)if (!flag[j] && map[j][i] != INF)map[j][i] -= map[pre[i]][i];for (j = pre[i]; j != i; j = pre[j]){for (k = 1; k <= n; k++)if (!flag[k] && map[j][k] != INF)map[i][k] = min(map[i][k], map[j][k]);for (k = 1; k <= n; k++)if (!flag[k] && map[k][j] != INF)map[k][i] = min(map[k][i], map[k][j] - map[pre[j]][j]);}break;}if (i>n)//说明没有环了。  {for (j = 2; j <= n; j++)if (!flag[j])ans += map[pre[j]][j];return ans;}}
}
int main()
{int i, j, x, y;while (scanf("%d%d", &n, &m) != -1){for (i = 1; i <= n; i++)scanf("%lf%lf", &a[i].x, &a[i].y);for (i = 1; i <= n; i++)for (j = 1; j <= n; j++)map[i][j] = INF;for (i = 1; i <= m; i++){scanf("%d%d", &x, &y);if (x == y)continue;//消除自环  map[x][y] = get_dis(a[x], a[y]);}if (!check())//检查有向图是否联通  {printf("poor snoopy\n");}else{printf("%.2lf\n", solve());}}
}