bzoj2260: 商店购物&&4349: 最小树形图

最小树形图问题啊

最小树形图是撒哩，就是给你一个有向图，确定一个根，要你到达所有点，那棵最短路径树的总边权

做这个用的是朱(jv)刘(lao)算法。

首先假如有多个联通块就无解啦

对应每个点（除了根），找到一条连向它的最短的边，假如没有环，那这个就是答案嘛

否则就找环，然后缩点，对于一个环，假如要从它的一个成员节点x断开，那么答案是减去环上的边，然后加上连进来的边，那么我们就把所有连向x的边的权，减去环上这条边的权（感觉很像数据备份退流的思想）

不断重复直到没有环。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

struct edge{int x,y;double d;}a[];int len;

void ins(int x,int y,double d)

{

    len++;

    a[len].x=x;a[len].y=y;a[len].d=d;

}

double rch[];int pre[];

int bel[],fr[];

double directed_MST(int n,int rt)

{

    double ans=;

    while()

    {

        memset(rch,0x7f,sizeof(rch));

        for(int i=;i<=len;i++)

            if(a[i].x!=a[i].y&&rch[a[i].y]>a[i].d)

                pre[a[i].y]=a[i].x, rch[a[i].y]=a[i].d;

        rch[rt]=;

        for(int i=;i<=n;i++)

            if(rch[i]==0x7f)return -;

        memset(bel,,sizeof(bel));

        memset(fr,,sizeof(fr));

        int cnt=;

        for(int i=;i<=n;i++)

        {

            ans+=rch[i];

            int k=i;

            while(fr[k]!=i&&bel[k]==&&k!=rt) fr[k]=i, k=pre[k];

            if(bel[k]==&&k!=rt)

            {

                cnt++;int t=k;

                do

                {

                    bel[k]=cnt;

                    k=pre[k];

                }while(k!=t);

            }

        }

        if(cnt==)return ans;

        for(int i=;i<=n;i++)

            if(bel[i]==)bel[i]=++cnt;

        for(int i=;i<=len;i++)

        {

            if(bel[a[i].x]!=bel[a[i].y])a[i].d-=rch[a[i].y];

            a[i].x=bel[a[i].x],a[i].y=bel[a[i].y];

        }

        n=cnt,rt=bel[rt];

    }

}

int tp,id[];

int cp[];double cnm[];

int main()

{

    int n,m,x,y,pp;double dd;

    scanf("%d",&n);tp=;

    for(int i=;i<=n;i++)

    {

        scanf("%lf%d",&dd,&pp);

        if(pp>)

        {

            id[i]=++tp;

            cnm[id[i]]=dd;

            cp[id[i]]=pp;

        }

    }

    n=tp+;len=;

    for(int i=;i<n;i++)ins(n,i,cnm[i]);

    scanf("%d",&m);

    for(int i=;i<=m;i++)

    {

        scanf("%d%d%lf",&x,&y,&dd);

        if(cp[id[x]]>&&cp[id[y]]>)

        {

            ins(id[x],id[y],dd);

            cnm[id[y]]=min(cnm[id[y]],dd);

        }

    }

    double ans=directed_MST(n,n);

    for(int i=;i<n;i++)

        ans+=(double(cp[i]-))*cnm[i];

    printf("%.2lf\n",ans);

    return ;

}