当前位置: 代码迷 >> 综合 >> poj 3164 Command Network 最小树形图
  详细解决方案

poj 3164 Command Network 最小树形图

热度:12   发布时间:2024-01-19 06:17:06.0

题意:

给一个有向图,求他的定点最小生成树。

分析:

有向图的定点最小生成树又称最小树形图,用朱刘算法解决,算法步奏详细解释:

  1. 首先判断是否存在最小树形图,从根结点dfs一遍。
  2. 除根节点外,对于其他所有顶点v,找一条最短的以v为终点的边。
  3. 判断步骤2中找的边是否会形成环,会成环转步骤4,不会转步骤5。
  4. 将环缩成一个点,更新该环与其他顶点之间的边权。
  5. sum+缩完点后的所有边权即为最小树形图答案。

代码:

//poj 3164
//sep9
#include <iostream>
#include <cmath>
#define INF 0x7fffffff 
using namespace std;const int maxN=128;
int n,m;
double x[maxN],y[maxN];
double g[maxN][maxN];
int vis[maxN];
int used[maxN],pass[maxN],eg[maxN],more,queue[maxN];
int map[maxN][maxN];void combine(int id,double &sum){int tot=0,from,i,j,k;for(;id!=0&&!pass[id];id=eg[id]){queue[tot++]=id;pass[id]=1;}	for(from=0;from<tot&&queue[from]!=id;++from);if(from==tot) return ;more=1;for(i=from;i<tot;++i){sum+=g[eg[queue[i]]][queue[i]];if(i!=from){used[queue[i]]=1;for(j=1;j<=n;++j) if(!used[j]){if(g[queue[i]][j]<g[id][j])g[id][j]=g[queue[i]][j];}	}}for(i=1;i<=n;++i) if(!used[i]&&i!=id){for(j=from;j<tot;++j){k=queue[j];if(g[i][id]>g[i][k]-g[eg[k]][k])g[i][id]=g[i][k]-g[eg[k]][k];}}
}double mdst(int root)
{int i,j,k;double sum=0;memset(used,0,sizeof(used));for(more=1;more;){more=0;memset(eg,0,sizeof(eg));for(i=1;i<=n;++i) if(!used[i]&&i!=root){for(j=1,k=0;j<=n;++j) if(!used[j]&&i!=j){if(k==0||g[j][i]<g[k][i])k=j;}eg[i]=k;	}memset(pass,0,sizeof(pass));for(i=1;i<=n;++i) if(!used[i]&&!pass[i]&&i!=root)combine(i,sum);}	for(i=1;i<=n;++i) if(!used[i]&&i!=root) sum+=g[eg[i]][i];return sum;	
}void dfs(int root)
{vis[root]=1;for(int i=1;i<=n;++i)if(map[root][i]==1&&vis[i]==0)dfs(i);	
}int main()
{while(scanf("%d%d",&n,&m)==2){int i,j;for(i=1;i<=n;++i)scanf("%lf%lf",&x[i],&y[i]);for(i=1;i<=n;++i)for(j=1;j<=n;++j)g[i][j]=INF;memset(map,0,sizeof(map));while(m--){scanf("%d%d",&i,&j);if(i==j) continue;g[i][j]=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));map[i][j]=1;}memset(vis,0,sizeof(vis));dfs(1);for(i=1;i<=n;++i)if(vis[i]==0)break;if(i<=n)printf("poor snoopy\n");elseprintf("%.2lf\n",mdst(1));		}	
} 



  相关解决方案