题目链接:传送门

Description

给你一棵无向带边权的仙人掌（节点数<=1e3），求前k(1<=k<=1e5)小生成树的权值 * k之和。

Solution

一开始看到这道题差点被仙人掌吓到了。。。 实际上由于这个图是仙人掌，那么它的生成树就一定是每个环去掉一条边所构成的， 我们可以通过存边的tarjan算法找到仙人掌上的所有环， 题目要求k小生成树，我们只要找到去掉的边的k大的组合即可。 那么就可把问题简化为：有一些集合，在每个集合中选一个数，求前k大的组合。 然后这就是一个很经典的问题了，直接用堆维护即可(证明见此)（一开始用的priority_queu发现被卡常，换成make_heap才卡进4000ms）

Code

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#include <bits/stdc++.h>

using namespace std;

const int Maxn = 1000 + 10, Maxm = 2000 + 10, Maxk = 1e5 + 10;

int N, M, K;
int e, Begin[Maxn], Next[Maxm * 2], To[Maxm * 2], W[Maxm * 2];
int Ans[Maxk], dfn[Maxn], low[Maxn], Index;
int tmp[Maxk], Sum;
stack <int> S;
struct node
{
    int val, pos1, pos2;
    bool operator < (const node &x) const
    {
        return x.val > val;
    }
}A[Maxk];

struct heap {
    int point;
    node data[Maxk];
    heap (){};
    inline int empty()
    {
        return !point;
    }
    inline void clear()
    {
        point = 0;
    }
    inline void push(node a) {
        data[++point] = a;
        push_heap(data + 1, data + point + 1);
    }
    inline node pop() {
        node res = data[1];
        pop_heap(data + 1, data + point + 1);
        --point;
        return res;
    }
    inline node top() {
        return data[1];
    }
}Q;

inline int read(){
    int x=0,w=1;
    char ch=0;
    while (ch<'0' || ch>'9'){
          if (ch=='-') w=-1;
          ch=getchar();
    }
    while (ch<='9' && ch>='0'){
          x=(x<<1)+(x<<3)+ch-'0';
          ch=getchar();
    }
    return x*w;
}

inline void Init ()
{
    e = Index = Sum = 0;
    for (int i = 1; i <= N; ++i) Begin[i] = dfn[i] = 0;
    Ans[0] = 0;
}

inline void add_edge (int x, int y, int z)
{
    To[++e] = y;
    Next[e] = Begin[x];
    Begin[x] = e;
    W[e] = z;
}

inline void Input ()
{
    while (M--)
    {
        int x, y, z;
        x = read(); y = read(); z = read();
        Sum += z;
        add_edge (x, y, z);
        add_edge (y, x, z);
    }
    K = read();
}

int save[Maxk];

inline void Calc ()
{
//  priority_queue <node> Q;
    Q.clear();
    for (int i = 1; i <= tmp[0]; ++i)
        Q.push((node){Ans[1] + tmp[i], 1, i});
    save[0] = 0;
    while (save[0] < K && !Q.empty())
    {
        node x = Q.top(); Q.pop();
        save[++save[0]] = x.val;
        if (x.pos1 + 1 <= Ans[0])
            Q.push((node){Ans[x.pos1 + 1] + tmp[x.pos2], x.pos1 + 1, x.pos2});
    }
    for (int i = 0; i <= save[0]; ++i)
        Ans[i] = save[i];
}

inline void tarjan (int x, int fa)
{
    dfn[x] = low[x] = ++Index;
    for (int i = Begin[x]; i; i = Next[i])
    {
        int y = To[i];
        if (y == fa) continue;
        if (!dfn[y])
        {
            S.push(i);
            tarjan(y, x);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x])
            {
                tmp[0] = 0;
                while (1)
                {
                    int a = S.top(); S.pop();
                    tmp[++tmp[0]] = W[a];
                    if (a == i) break;
                }
                if (tmp[0] > 1) Calc();
            }
        }
        else if (dfn[y] < dfn[x])
            S.push(i), low[x] = min(low[x], dfn[y]);
    }
}

int tot;
inline void Solve ()
{
    Ans[++Ans[0]] = 0;
    tarjan(1, -1);
    unsigned ans = 0;
    for (int i = 1; i <= Ans[0]; ++i)
        ans += i * (Sum - Ans[i]);
    printf("Case #%d: %u\n", ++tot, ans);
}

int main()
{
#ifdef hk_cnyali
    freopen("A.in", "r", stdin);
    freopen("A.out", "w", stdout);
#endif
    while (~scanf("%d%d", &N, &M))
    {
        Init();
        Input();
        Solve();
    }
    return 0;
}