朱刘算法


朱刘算法


概述

朱刘算法也称为有向图的最小生成树,我们把其中的图称为最小树形图。它的特点是没有环,同时除了起始点外每一个点的入度都为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;
}


文章作者: Dydong
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 Dydong !
  目录