最小树形图--朱刘算法([JSOI2008]小店购物)

时间：2023-12-17 17:28:26

题面

luogu

Sol

首先设一个 \(0\) 号点，向所有点连边，表示初始价值

显然这个图的一个 \(0\) 为根的最小有向生成树的边权和就是每个买一次的最小价值

再买就一定能优惠(包含 \(0\) 的边)

有向图最小生成树？？？

朱刘算法

其实正确性不会理论。。

可以说是一个不断调整的过程，从而得到最优解

时间复杂度 \(O(VE)\)

流程：

1.去掉自环

2.先给每个点选择一条最小的入边，并记录连过来的点

3.如果此时有点没有入边(除根以外)，那么显然无解

4.算上每个点入边贡献，加入答案

5.如果没有有向环，那么做完结束

6.如果有，缩点，并且把连出去的边都减去连出去那个点的入边，因为贡献算过了

7.存储新图，对新图重复所有操作

Code

# include <bits/stdc++.h>

# define IL inline

# define RG register

# define Fill(a, b) memset(a, b, sizeof(a))

using namespace std;

typedef long long ll;

const int maxn(100005);

const double inf(1e9);

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];

IL void DirectedMST(){

    RG int num = n, rt = 1, idx;

    while(true){

        // 初始化

        for(RG int i = 1; i <= num; ++i) id[i] = vis[i] = pre[i] = -1, inw[i] = inf;

        // 选入边

        for(RG 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(RG int i = 1; i <= num; ++i){

            ans += inw[i];

            if(vis[i] == -1){

                RG int nw = i;

                while(vis[nw] == -1) vis[nw] = i, nw = pre[nw];

                if(vis[nw] == i && nw != rt){

                    id[nw] = ++idx;

                    for(RG int j = pre[nw]; j != nw; j = pre[j]) id[j] = idx;

                }

            }

        }

        // 没有环结束

        if(!idx) return;

        // 重标号，记录新图

        for(RG int i = 1; i <= num; ++i) if(id[i] == -1) id[i] = ++idx;

        for(RG 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(RG 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(RG 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(RG int i = 2; i <= n; ++i) ans += (need[i] - 1) * cost[i];

    DirectedMST();

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

    return 0;

}

相关文章