「HDU-2121」Ice_cream’s world II(不定根最小树形图)

发表于 | 分类于 ，

「HDU-2121」Ice_cream’s world II
朱刘算法，不定根最小树形图

题意

给定一个有向图，选择一个点使其能到达其他所有点，并使花费最小，输出最小花费。如果有多个这样的点，输出编号小的点。如果没有这样的点，输出impossible.

思路

不定根最小生成树模板题。

设定一个虚根并向所有结点连边，边权为图上所有边的边权之和$sum+1$，以虚根为$root$跑一遍朱刘算法。

如果求出的边权之和$res>=2*sum$，说明至少有两个结点是从虚根出发到达的点，即原图不连通。

原图连通的状态下，只有一个点是从虚根出发到达的点。在跑最小树形图时记录从虚根出发到达的点，即为原图的根。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>

using namespace std;

const long long INF = 1e17;
const int maxn = 1000 + 10;

struct Edge { int u, v; long long cost; } edge[maxn * maxn];

int pre[maxn], vis[maxn], id[maxn], pos;
long long in[maxn];

long long zhuliu(int root, int n, int m)
{
    long long res = 0;
    int u, v;
    for (;;)
    {
        for (int i = 0; i < n; i++) in[i] = INF;
        for (int i = 0; i < m; i++)
            if (edge[i].u != edge[i].v && edge[i].cost < in[edge[i].v])
            {
                pre[edge[i].v] = edge[i].u;
                in[edge[i].v] = edge[i].cost;
                if (edge[i].u == root) pos = i;
            }
        for (int i = 0; i < n; i++) if (i != root && in[i] == INF) return -1;
        int tn = 0;
        memset(id, 0xff, sizeof id);
        memset(vis, 0xff, sizeof vis);
        in[root] = 0;
        for (int i = 0; i < n; i++)
        {
            res += in[i];
            v = i;
            while (vis[v] != i && id[v] == -1 && v != root) vis[v] = i, v = pre[v];
            if (v != root && id[v] == -1)
            {
                for (int u = pre[v]; u != v; u = pre[u]) id[u] = tn;
                id[v] = tn++;
            }
        }
        if (tn == 0) break;
        for (int i = 0; i < n; i++) if (id[i] == -1) id[i] = tn++;
        for (int i = 0; i < m; i++)
        {
            v = edge[i].v;
            edge[i].u = id[edge[i].u];
            edge[i].v = id[edge[i].v];
            edge[i].cost -= in[v];
        }
        n = tn;
        root = id[root];
    }
    return res;
}

int main()
{
    int n, m;
    while (scanf("%d%d", &n, &m) != EOF)
    {
        long long sum = 0;
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%lld", &edge[i].u, &edge[i].v, &edge[i].cost);
            edge[i].u++;
            edge[i].v++;
            sum += edge[i].cost;
        }
        sum++;
        int root = 0;
        for (int i = m; i < m + n; i++)
            edge[i].u = root, edge[i].v = i - m + 1, edge[i].cost = sum;
        long long res = zhuliu(root, n + 1, m + n);
        if (res == -1 || res - sum >= sum) printf("impossible\n\n");
        else printf("%lld %d\n\n", res - sum, pos - m);
    }
    return 0;
}