本文主要是介绍POJ-3164 Command Network 最小树形图 朱刘算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
朱刘算法
参考之 http://blog.csdn.net/wsniyufang/article/details/6747392
http://blog.csdn.net/ac_lion/article/details/8104461
#include<stdio.h>
#include<string.h>
#include<vector>
#include<math.h>
using namespace std;
const int maxn = 115;
#define type double
const type inf = 1<<30;
int n,m;
struct point
{double x,y;
}p[maxn];
struct node
{int u,v;type w;
}E[maxn*maxn];
int pre[maxn],id[maxn],vis[maxn];//id为缩点后的点
type in[maxn]; //in[i]点i的最小入边权
double getdis(point a,point b)
{ return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
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; 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 = E[i].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]; //这里的v不能直接用E[i].v} } nv = cntnode; root = id[root]; } return ret;
}
int main()
{//freopen("data.txt","r",stdin);while( scanf("%d%d",&n,&m) != EOF ){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 = getdis(p[E[i].u],p[E[i].v]);elseE[i].w = inf;}type ans = Directed_MST(0,n,m); if( ans == -1 ) printf("poor snoopy\n"); else printf("%.2f\n",ans); }return 0;
}这篇关于POJ-3164 Command Network 最小树形图 朱刘算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
