[POJ 3164] Command Network 有向图的最小树形图(朱刘算法)
Command Network
题目链接:http://poj.org/problem?id=3164
题目大意:
========================== 分割线之下摘自Sasuke_SCUT的blog==================================================
最 小树形图,就是给有向带权图中指定一个特殊的点root,求一棵以root为根的有向生成树T,并且T中所有边的总权值最小。最小树形图的第一个算法是 1965年朱永津和刘振宏提出的复杂度为O(VE)的算法。
判断是否存在树形图的方法很简单,只需要以v为根作一次图的遍历就可以了,所以下面的 算法中不再考虑树形图不存在的情况。
在所有操作开始之前,我们需要把图中所有的自环全都清除。很明显,自环是不可能在任何一个树形图上的。只有进 行了这步操作,总算法复杂度才真正能保证是O(VE)。
首先为除根之外的每个点选定一条入边,这条入边一定要是所有入边中最小的。现在所有的最小 入边都选择出来了,如果这个入边集不存在有向环的话,我们可以证明这个集合就是该图的最小树形图。这个证明并不是很难。如果存在有向环的话,我们就要将这 个有向环所称一个人工顶点,同时改变图中边的权。假设某点u在该环上,并设这个环中指向u的边权是in[u],那么对于每条从u出发的边(u, i, w),在新图中连接(new, i, w)的边,其中new为新加的人工顶点; 对于每条进入u的边(i, u, w),在新图中建立边(i, new, w-in[u])的边。为什么入边的权要减去in[u],这个后面会解释,在这里先给出算法的步骤。然后可以证明,新图中最小树形图的权加上旧图中被收缩 的那个环的权和,就是原图中最小树形图的权。
上面结论也不做证明了。现在依据上面的结论,说明一下为什么出边的权不变,入边的权要减去in [u]。对于新图中的最小树形图T,设指向人工节点的边为e。将人工节点展开以后,e指向了一个环。假设原先e是指向u的,这个时候我们将环上指向u的边 in[u]删除,这样就得到了原图中的一个树形图。我们会发现,如果新图中e的权w‘(e)是原图中e的权w(e)减去in[u]权的话,那么在我们删除 掉in[u],并且将e恢复为原图状态的时候,这个树形图的权仍然是新图树形图的权加环的权,而这个权值正是最小树形图的权值。所以在展开节点之后,我们 得到的仍然是最小树形图。逐步展开所有的人工节点,就会得到初始图的最小树形图了。
如果实现得很聪明的话,可以达到找最小入边O(E),找环 O(V),收缩O(E),其中在找环O(V)这里需要一点技巧。这样每次收缩的复杂度是O(E),然后最多会收缩几次呢?由于我们一开始已经拿掉了所有的 自环,我门可以知道每个环至少包含2个点,收缩成1个点之后,总点数减少了至少1。当整个图收缩到只有1个点的时候,最小树形图就不不用求了。所以我们最 多只会进行V-1次的收缩,所以总得复杂度自然是O(VE)了。由此可见,如果一开始不除去自环的话,理论复杂度会和自环的数目有关。
======================== 分割线之上摘自Sasuke_SCUT的blog=====================================================
下 面是朱刘算法的构造图
#include<iostream> #include<fstream> #include<cstdio> #include<cstring> #include<cmath> #include<map> #include<queue> #include<stack> #include<vector> #include<set> #include<ctype.h> #include<algorithm> #include<string> #define PI acos(-1.0) #define maxn 110 #define INF 1<<25 #define mem(a, b) memset(a, b, sizeof(a)) typedef long long ll; typedef double type; using namespace std; int n, m; struct point { double x, y; }p[maxn]; struct node { int u, v; type w; }e[maxn * 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)); } void init() { 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", &e[i].u, &e[i].v); e[i].u--, e[i].v--; if (e[i].u != e[i].v) e[i].w = dis(p[e[i].u], p[e[i].v]); else e[i].w = INF; // 去除自环 } } int pre[maxn], id[maxn], vis[maxn]; type in[maxn]; type Directed_MST(int root, int NV, int NE) { type ret = 0; while(true) { //1.找最小入边 for (int i = 0; i < NV; i++) in[i] = INF; for (int i = 0; i < NE; i++) { int u = e[i].u; int v = e[i].v; if(e[i].w < in[v] && u != v) { pre[v] = u; in[v] = e[i].w; } } for (int i = 0; i < NV; i++) { if(i == root) continue; if(in[i] == INF) return -1; //除了根以外有点没有入边,则根无法到达它 } //2.找环 int cntnode = 0; mem(id,-1); mem(vis, -1); in[root] = 0; for (int i = 0; i < NV; i++) {//标记每个环 ret += 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] = cntnode; id[v] = cntnode ++; } } if(cntnode == 0) break;//无环 for (int i = 0; i < NV; i++) if(id[i] == -1) id[i] = cntnode ++; //3.缩点,重新标记 for (int i = 0; i < NE; i++) { int v = e[i].v; e[i].u = id[e[i].u]; e[i].v = id[e[i].v]; if(e[i].u != e[i].v) e[i].w -= in[v]; } NV = cntnode; root = id[root]; } return ret; } int main () { while(scanf("%d%d", &n, &m) != EOF) { init(); type ans = Directed_MST(0, n, m); if (ans == -1) puts("poor snoopy"); else printf("%.2f\n", ans); } return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。