題目大意：給定一個有向圖，根節點已知，求該有向圖的最小樹形圖。最小樹形圖即有向圖的最小生成樹，定義為：選擇一些邊，使得根節點能夠到達圖中所有的節點，并使得選出的邊的邊權和最小。
題目算法：朱-劉算法（即由中國人朱永津和劉振宏共同發明的算法）。
算法步驟如下：
1.判斷圖的連通性，若不連通直接無解，否則一定有解。
2.為除了根節點以外的所有點選擇一個權值最小的入邊，假設用pre數組記錄前驅，f數組記錄選擇的邊長，記所選邊權和為temp。
3.（可利用并查集）判斷選擇的的邊是否構成環，若沒有則直接ans+=temp并輸出ans，若有，則進行下一步操作。
4.對該環實施縮點操作，設該環上有點V1，V2……Vi……Vn，縮成的點為node ，對于所有不在環中的點P進行如下更改：
（1） 點P到node的距離為min{a[p,Vi]-f[Vi]} (a為邊集數組)
（2）點node到p的距離為min{a[Vi,p]}
操作（1）的了解：先假設環上所有邊均選上，若下次選擇某一條邊進入該環，則可以斷開進入點與進入點的前驅之間的邊，即斷開F[進入點]，是以等效為直接把a[p,node]指派為min{a[p,Vi]-f[Vi]}。
特别提醒：本題有自環，可以提前删掉，因為它沒有用。
最後G++double輸出lf會wa，改成f就好了，或者用c++送出
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<cassert>
#include<iomanip>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pi acos(-1)
#define ll long long
#define mod 1000000007
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const double g=10.0,eps=1e-9;
const int N=100+10,maxn=100000+10,inf=0x3f3f3f;
double x[N],y[N];
int n,m;
int pre[N];
bool vis[N],in[N];
double w[N][N];
double dis(int a,int b)
{
return sqrt((x[a]-x[b])*(x[a]-x[b])+(y[a]-y[b])*(y[a]-y[b]));
}
void dfs(int u)
{
vis[u]=1;
for(int i=1;i<=n;i++)
if(!vis[i]&&w[u][i]<inf)
dfs(i);
}
double dirmst(int u)
{
double ans=0;
dfs(u);
for(int i=1;i<=n;i++)
if(!vis[i])
return -1;
memset(vis,0,sizeof vis);
while(1){
for(int i=1;i<=n;i++)
{
if(i!=u&&!in[i])
{
w[i][i]=inf;
pre[i]=i;
for(int j=1;j<=n;j++)
if(!in[j]&&w[j][i]<w[pre[i]][i])
pre[i]=j;
}
}
int i;
for(i=1;i<=n;i++)
{
if(i!=u&&!in[i])
{
int j=i,cnt=0;
while(j!=u&&pre[j]!=i&&cnt<=n)cnt++,j=pre[j];
if(j==u||cnt>n)continue;
break;
}
}
if(i>n)
{
for(int j=1;j<=n;j++)
if(j!=u&&!in[j])
ans+=w[pre[j]][j];
return ans;
}
int j=i;
memset(vis,0,sizeof vis);
do{
ans+=w[pre[j]][j],j=pre[j],vis[j]=in[j]=1;
}while(j!=i);
in[i]=0;
for(int k=1;k<=n;k++)
if(vis[k])
for(int j=1;j<=n;j++)
if(!vis[j])
{
if(w[i][j]>w[k][j])w[i][j]=w[k][j];
if(w[j][k]<inf&&w[j][k]-w[pre[k]][k]<w[j][i])
w[j][i]=w[j][k]-w[pre[k]][k];
}
}
return ans;
}
int main()
{
/* ios::sync_with_stdio(false);
cin.tie(0);
cout<<setiosflags(ios::fixed)<<setprecision(2)<<endl;*/
while(~scanf("%d%d",&n,&m)){
for(int i=1;i<=n;i++)
scanf("%lf%lf",&x[i],&y[i]);
for(int i=1;i<=n;i++)
{
vis[i]=in[i]=0;
for(int j=1;j<=n;j++)
w[i][j]=inf;
}
while(m--){
int a,b;
scanf("%d%d",&a,&b);
if(a==b)continue;
w[a][b]=dis(a,b);
}
/* for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
cout<<w[i][j]<<" ";
cout<<endl;
}*/
double ans=dirmst(1);
if(ans<0)printf("poor snoopy
");
else printf("%.2f
",ans);
}
return 0;
} 最小樹形圖