最小有向生成树：给定一个有向图G和其中一个节点u，找出以u为根节点的权和最小有向生成树。 有向生成树（树形图），满足以下条件： 有且仅有一个入读为0的节点，为根节点； 其他节点入度均为1； 从根节点可以遍历其他节点。 此类问题可采用朱刘算法来解决（中国人发明的算法~~~） 预处理：删除自环并dfs一遍，判断是否存在解。 然后给所有非根节点选一条权最小的入边，判断这些边是否构成环，是则累加边权，缩点，继续该过程，直到图中不存在环为止。注意每次缩点后，对于环上任意一点v，设其在环上的入点为u，权值为q，则所有指向v的边权值均要减去q。这是因为如果后面将u更新到为u’，则答案不应加上q的值，所以要先减去一个q，这样相加时就可以抵消了……
//POJ 3164#include <cstdio>#include <algorithm>#include <cstring>#define maxn 105#define maxm 10000+5#include <cmath>#define INF (1<<30)using namespace std;int id[maxn],root,cir,g,num,head[maxn],n,m,vis[maxn],u,v,suo[maxn],PRe[maxn];double ans,val[maxn],x[maxn],y[maxn];struct xx{ int u,v,next; double q;}b[maxm];void add(int u,int v,double q){ b[++num]=(xx){u,v,head[u],q}; head[u]=num;}void dfs(int t){ for (int k=head[t];k!=0;k=b[k].next) if (vis[b[k].v]) g++,vis[b[k].v]=0,dfs(b[k].v);}int main(){ while (scanf("%d%d",&n,&m)==2) { num=ans=0; g=1; memset(head,0,sizeof(head)); memset(vis,-1,sizeof(vis)); for ( int i=1;i<=n;i++) scanf("%lf%lf",&x[i],&y[i]); for ( int i=0;i<m;i++) { scanf("%d%d",&u,&v); //if (u!=v) add(u,v,sqrt((x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]))); } vis[1]=0;dfs(1); if (g!=n) { printf("poor snoopy/n"); continue; } root=1; for (;;) { cir=0; for (int i=1;i<=n;i++) val[i]=INF; memset(id,-1,sizeof(id)); memset(vis,-1,sizeof(vis)); for (int k=1;k<=num;k++) if (b[k].q<val[b[k].v]&&b[k].u!=b[k].v)pre[b[k].v]=b[k].u,val[b[k].v]=b[k].q; val[root]=0; for (int i=1;i<=n;i++) { ans+=val[v=i]; while (vis[v]!=i&&id[v]==-1&&v!=root) vis[v]=i,v=pre[v];//? if (v!=root&&id[v]==-1){ cir++;u=pre[v];id[v]=cir; while (u!=v)id[u]=cir,u=pre[u]; } } if (cir==0) break; for (int i=1;i<=n;i++)if (id[i]==-1) id[i]=++cir; for (int k=1;k<=num;k++) { b[k].q-=val[b[k].v]; b[k].u=id[b[k].u]; b[k].v=id[b[k].v]; } root=id[root];n=cir; } printf("%.2f/n",ans); } return 0;}新闻热点
疑难解答
