朱刘算法
概述
朱刘算法也称为有向图的最小生成树,我们把其中的图称为最小树形图。它的特点是没有环,同时除了起始点外每一个点的入度都为1。它的算法流程是这样的:1.对于每一个点找一条入边为权值最小的边。2.判断选出的边是否存在环,如果无环则直接break,因为它是一个最优的同时满足最小树形图的条件图。3.如果存在环我们先把所有的环缩点,res迭代加上环的权值,此时我们只要删一条环里的边即可,我们把环内的边删去,终点在环里的边边权减去w环,其他边不用动,这样我们只要把修改的边权差值加到新的边上。
模板(avwing2417)
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
const int N = 110;
const double inf = 1e8+10;
typedef pair<double,double> PII;
int n,m;
bool g[N][N];
double d[N][N],bd[N][N];
int pre[N],bpre[N];
int dfn[N],low[N],ts,stk[N],top;
int id[N],cnt;
PII q[N];
bool st[N],ins[N];
void dfs(int u)
{
st[u]=true;
for(int i=1;i<=n;i++)
if(g[u][i]&&!st[i])
dfs(i);
}
bool check_con()
{
memset(st,false,sizeof st);
dfs(1);
for(int i=1;i<=n;i++)
if(!st[i]) return false;
return true;
}
void tarjan(int u)
{
dfn[u]=low[u]=++ts;
stk[++top]=u,ins[u]=true;
int j=pre[u];
if(!dfn[j])
{
tarjan(j);
low[u]=min(low[u],low[j]);
}
else if(ins[j]) low[u]=min(low[u],dfn[j]);
if(low[u]==dfn[u])
{
int y;
++cnt;
do{
y=stk[top--];
ins[y]=false;
id[y]=cnt;
}
while(y!=u);
}
}
double get_dist(int i,int j)
{
double dx=q[i].x-q[j].x;
double dy=q[i].y-q[j].y;
return sqrt(dx*dx+dy*dy);
}
double work()
{
double res=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(g[i][j]) d[i][j]=get_dist(i,j);
else d[i][j]=inf;
while(true)
{
for(int i=1;i<=n;i++)
{
pre[i]=i;
for(int j=1;j<=n;j++)
if(d[pre[i]][i]>d[j][i])
pre[i]=j;
}
memset(dfn,0,sizeof dfn);
ts=cnt=0;
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i);
if(cnt==n)
{
for(int i=2;i<=n;i++) res+=d[pre[i]][i];
break;
}
for(int i=2;i<=n;i++)
if(id[pre[i]]==id[i])
res+=d[pre[i]][i];
for(int i=1;i<=cnt;i++)
for(int j=1;j<=cnt;j++)
bd[i][j]=inf;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(d[i][j]<inf&&id[i]!=id[j])
{
int a=id[i],b=id[j];
if(id[pre[j]]==id[j]) bd[a][b]=min(bd[a][b],d[i][j]-d[pre[j]][j]);
else bd[a][b]=min(bd[a][b],d[i][j]);
}
n=cnt;
memcpy(d,bd,sizeof d);
}
return res;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(g,false,sizeof g);
for(int i=1;i<=n;i++) scanf("%lf%lf",&q[i].x,&q[i].y);
while(m--)
{
int a,b;
scanf("%d%d",&a,&b);
if(a!=b&&b!=1) g[a][b]=true;
}
if(!check_con()) puts("poor snoopy");
else printf("%.2lf\n",work());
}
return 0;
}