题解 P2792 【[JSOI2008]小店购物】

· · 题解

最小树形图--朱刘算法

通过不断调整来实现最优解。

大致思路如下：

首先去掉自环。

用贪心的思想给每个点选择一条最小的入边，记录连接的点。

特判此时如果有点没有入边(除根以外)，显而易见此时无解。 算上每个点入边的代价，统计答案。

此时判定有没有有向环，如果没有直接输出。 如果有有向环，缩点，并且把连出去的边都减去连出去的点的入边，因为代价已经统计。 二次建图（或多次），对新图重复所有操作。

code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100010;
const double inf=0x7f7f7f;
int n,tot,m,cnt,need[maxn],pre[maxn],vis[maxn],id[maxn];
double ans,cost[maxn],prize,inw[maxn];
struct Edge{
    int u,v;
    double w;
}e[maxn];
inline void mst(){
    register int num=n,rt=1,idx;
    while(1){// 初始化
        for(register int i=1;i<=num;++i) id[i]=vis[i]=pre[i]=-1,inw[i]=inf;// 选入边
        for(register int i=1;i<=cnt;++i)
            if(inw[e[i].v]>e[i].w&&e[i].u!=e[i].v) inw[e[i].v]=e[i].w,pre[e[i].v]=e[i].u;
        pre[rt]=rt,idx=inw[rt]=0;// 缩环，统计贡献
        for(register int i=1;i<=num;++i){
            ans+=inw[i];
            if(vis[i]==-1){
                register int nw=i;
                while(vis[nw]==-1) vis[nw]=i,nw=pre[nw];
                if(vis[nw]==i&&nw!=rt){
                    id[nw]=++idx;
                    for(register int j=pre[nw];j!=nw;j=pre[j]) id[j]=idx;
                }
            }
        }// 没有环结束
        if(!idx) return; // 重标号，记录新图
        for(register int i=1;i<=num;++i) if(id[i]==-1) id[i]=++idx;
        for(register int i=1;i<=cnt;++i)
            e[i].w -=inw[e[i].v],e[i].u=id[e[i].u],e[i].v=id[e[i].v];
        num=idx,rt=id[rt];
    }
}

int main(){
    scanf("%d",&tot),n=2;
    for(register int i=1;i<=tot;++i){
        scanf("%lf%d",&cost[n],&need[n]);
        if(need[n]) e[++cnt]=(Edge){1,n,cost[n]},vis[i]=n++;
    }
    --n,scanf("%d",&m);
    for(register int i=1,a,b;i<=m;++i){
        scanf("%d%d%lf",&a,&b,&prize);
        a=vis[a],b=vis[b];
        if(a && b){
            cost[b]=min(cost[b],prize);
            e[++cnt]=(Edge){a,b,prize};
        }
    }
    for(register int i=2;i<=n;++i) ans+=(need[i]-1)*cost[i];
    mst();
    printf("%.2lf\n",ans);
    return 0;
}