首页 > 代码库 > POJ--3164--Command Network【朱刘算法】最小树形图
POJ--3164--Command Network【朱刘算法】最小树形图
链接:http://poj.org/problem?id=3164
题意:告诉n个点坐标,m条边表示两个点之间有路。从1点開始建立一个有向图最小生成树。
朱刘算法模板题
========================== 切割线之下摘自
user_id=Sasuke_SCUT" style="color:rgb(202,0,0); text-decoration:none; font-family:Arial; font-size:14px; line-height:26px">Sasuke_SCUT的blog==================================================
最 小树形图,就是给有向带权图中指定一个特殊的点root,求一棵以root为根的有向生成树T。而且T中全部边的总权值最小。最小树形图的第一个算法是 1965年朱永津和刘振宏提出的复杂度为O(VE)的算法。
推断是否存在树形图的方法非常easy,仅仅须要以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)了。由此可见。假设一開始不除去自环的话。理论复杂度会和自环的数目有关。
======================== 切割线之上摘自
user_id=Sasuke_SCUT" style="color:rgb(202,0,0); text-decoration:none; font-family:Arial; font-size:14px; line-height:26px">Sasuke_SCUT的blog=====================================================
简单的说就是除源点外每一个点选一条权值最小的入边,假设存在环则说明还存在多余的边,把成环的点缩成一个点再进行一遍生成树,直到没有环。
朱刘算法模板,顶点下标从0開始
/* 最小树形图图模版-朱刘算法 模版说明:点标号必须0-(N-1) 必须去除到自身的点(到自身的边的边权赋无限大) */ #include<cstring> #include<string> #include<fstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 50100 #define eps 1e-7 #define INF 0x7FFFFFFF #define seed 131 #define mod 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 struct node{ int u,v; double dis; }edge[10100]; int pre[110],ID[110],vis[110]; int n,m; int x[110],y[110]; double In[110]; double Directed_MST(int root,int NV,int NE) { double ret = 0; while(true) { //1.找最小入边 for(int i=0;i<NV;i++) In[i] = INF; for(int i=0;i<NE;i++){ int u = edge[i].u; int v = edge[i].v; if(edge[i].dis < In[v] && u != v) { pre[v] = u; In[v] = edge[i].dis; } } for(int i=0;i<NV;i++) { if(i == root) continue; if(In[i] == INF) return -1;//除了根以外有点没有入边,则根无法到达它 } //2.找环 int cntnode = 0; memset(ID,-1,sizeof(ID)); memset(vis,-1,sizeof(vis)); 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 = edge[i].v; edge[i].u = ID[edge[i].u]; edge[i].v = ID[edge[i].v]; if(edge[i].u != edge[i].v) { edge[i].dis -= In[v]; } } NV = cntnode; root = ID[root]; } return ret; } int main(){ int i,j,a,b; double temp; while(scanf("%d%d",&n,&m)!=EOF){ for(i=1;i<=n;i++){ scanf("%d%d",&x[i],&y[i]); } for(i=0;i<m;i++){ scanf("%d%d",&a,&b); edge[i].u = a - 1; edge[i].v = b - 1; if(a==b) edge[i].dis = INF; else{ temp = (x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]); temp = sqrt(temp); edge[i].dis = temp; } } double ans = Directed_MST(0,n,m); if(ans==-1) puts("poor snoopy"); else printf("%.2lf\n",ans); } return 0; }
POJ--3164--Command Network【朱刘算法】最小树形图