最小有向生成樹：給定一個有向圖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;}新聞熱點
疑難解答
