多校第一场的小锅，因为就算给我时间我也写不出来的题……算是小锅吧，还有三个大锅在背上。
开头先说一声，薛昊这个坑比，woc，跟我说这里的k小生成树是就是先取一个最小的，连上每一条边……
然后我在用优先队列的时候我就真的先推小的……
md debug好久才发现……醉了。
题意：
给你一个仙人掌图，要你求出前k小的生成树。将之与k相乘求和 mod 2 ^ 32
思路：
如果是一个一般图，那问题将非常困难，但他是一个仙人掌图，对于一个生成树来说，整张图的桥必定不能删掉，所以必须从每一个环中删掉一条边，而我们删掉的边要求前k大。
将每一个环的边作为集合，多个集合合并，求出前k大，这是一个经典问题。
方法是对每两个集合两两合并，将两个集合的边各自相连，用优先队列推出前k大，但这样时间和空间复杂度都很高。
一个与优先队列思想相似并且简单的方法就是，我们将旧集合维护有序，在这里为降序，并用一个优先队列存储两集合权值和。
首先将新集合的每个元素与旧集合最大元素(就是首位置)相加并加入队列。每次推出一个最大元素的时候，都将这个最大元素在新集合的原元素与旧集合相应元素的下一个元素相加加入队列。
以此推出k个元素存入集合。
这里写的是暴力求解法，tarjan求解接近tle边缘……
这里有个小技巧，就是我们要对结果取 2^ 32 膜 ， 值得注意的是 int 存储的总数就是 2 ^ 32 ,而 unsighed int 的范围则刚好是 [ 0 , 2 ^ 32) 所以我们只要用一个int存储，输出 用 %u 就会为我们自动按要求取 膜 。这应该是出题人特意设置的。但的确很妙。
AC Code
#include <cstdio>
#include <cstring>
#include <queue>
#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))
using namespace std;
const int max_n = 1010;
const int max_k = 1e5 + 5;
int n, m, k, idx, sum, cnt;
int head[max_n], fa[max_n], dep[max_n], eval[max_n], down[max_n];
int dsu[max_n];
int roll[3][max_k], cur, pre = 1;
struct Edge {
int to, next, weight;
Edge() {}
Edge(int _to, int _next, int _weight) { to = _to, next = _next, weight = _weight; }
} edges[max_n << 1];
struct NonTreeEdge {
int from, to, weight;
NonTreeEdge() {}
NonTreeEdge(int _from, int _to, int _weight) { from = _from, to = _to, weight = _weight; }
} NTedges[max_n];
struct node {
int val, pos;
node() {}
node(int _val, int _pos) { val = _val, pos = _pos; }
bool operator<(const node& a) const { return val < a.val; }
};
priority_queue<node> que;
int addEdge(int u, int v, int w)
{
edges[idx] = Edge(v, head[u], w);
head[u] = idx++;
edges[idx] = Edge(u, head[v], w);
head[v] = idx++;
return 0;
}
int dsuFind(int u) { return dsu[u] < 0 ? u : dsu[u] = dsuFind(dsu[u]); }
bool dsuMerge(int u, int v)
{
u = dsuFind(u), v = dsuFind(v);
if (u == v)
return false;
dsu[u] = v;
return true;
}
void dfs(int u)
{
for (int id = head[u]; ~id; id = edges[id].next) {
int v = edges[id].to;
if (v == fa[u])
continue;
fa[v] = u;
dep[v] = dep[u] + 1;
eval[v] = edges[id].weight;
dfs(v);
}
}
inline void read(int& x)
{
x = 0;
char ch = getchar();
while (ch < '0' || ch > '9')
ch = getchar();
while (ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0';
ch = getchar();
}
}
int main()
{
int u, v, w, cas = 0;
while (scanf("%d %d", &n, &m) != EOF) {
fill(head, -1), fill(dsu, -1), idx = cnt = sum = 0;
while (m--) {
read(u), read(v), read(w);
sum += w;
dsuMerge(u, v) ? addEdge(u, v, w) : (NTedges[cnt++] = NonTreeEdge(u, v, w), 1);
}
dfs(1);
read(k);
roll[cur][0] = 1, roll[cur][1] = 0;
for (int id = 0; id < cnt; id++) {
int u = NTedges[id].from, v = NTedges[id].to, &sz = roll[2][0] = 1;
roll[2][1] = NTedges[id].weight;
while (dep[u] > dep[v])
roll[2][++sz] = eval[u], u = fa[u];
while (dep[u] < dep[v])
roll[2][++sz] = eval[v], v = fa[v];
while (u != v) {
roll[2][++sz] = eval[u];
roll[2][++sz] = eval[v];
u = fa[u], v = fa[v];
}
cur ^= 1, pre ^= 1;
while (!que.empty())
que.pop();
for (int i = 1; i <= sz; i++) {
down[i] = 1;
que.push(node(roll[2][i] + roll[pre][1], i));
}
for (int& i = roll[cur][0] = 0; i < k && !que.empty();) {
int val = que.top().val, pos = que.top().pos;
que.pop();
roll[cur][++i] = val;
if (down[pos] < roll[pre][0]) {
val = roll[2][pos] + roll[pre][++down[pos]];
que.push(node(val, pos));
}
}
}
int ans = 0;
for (int i = roll[cur][0], tmp = 0; i > 0; i--) {
tmp += sum - roll[cur][i];
ans += tmp;
}
printf("Case #%d: %u\n", ++cas, ans);
}
return 0;
}