2017 多校2 I Curse Myself(第k小生成树)
题目: 给一张带权无向连通图，该图的任意一条边最多只会经过一个简单环，定义\(V(k)为第k小生成树的权值和\)，求出\(\sum_{k=1}^{K}k \cdot V(k) mod 2^{32}\)
思路： 比赛的时候看了一眼，没有看清楚是仙人掌那句话，觉得好难啊
看完题解之后觉得就算看清了还是过不了嘛。
直接上题解
由于图是一个仙人掌，所以显然对于图上的每一个环都需要从环上取出一条边删掉。所以问题就变为有 M 个集合，每个集合里面都有一堆数字，要从每个集合中选择一个恰好一个数加起来。求所有的这样的和中，前 K 大的是哪些。这就是一个经典问题了。
对所有集合两个两个进行合并，设当前合并的集合是 A 和BB，合并的过程中用堆来求出当前 \(A_{i} + B_{j}\)
这样的复杂度看起来是\(\mathcal{O}(MK \log K)\)，但如果合并的时候保证堆内的元素个数是新集合里的元素个数，设每个集合的大小分别为 \(m_{0}, m_{1}, \cdots, m_{M-1}\)
，则复杂度为 \(\mathcal{O}(\sum{K \log{m_{i}}}) = \mathcal{O}(K \log{\prod{m_i}})\)。当 \(m_{i}\)
都相等时取得最大值 \(\mathcal{O}\left(MK \log{\frac{\sum{m_i}}{M}}\right)\)，所以实际复杂度为 \(\mathcal{O}(MK)\)。
就照着题解敲了一遍，该优化的地方优化了，
找环那里用时间戳的方法一直没写对，所以换成直接用树再加边的方法去暴力找环了。
合并有序表的问题 刘汝佳的书上有讲
#include<bits/stdc++.h>
#define LL long long
#define P pair<int,int>
using namespace std;
const LL mod = (1LL<<32);
const int N = 1200;
const int M = 4 * N;
int n, m, K;
int read(){
int x = 0;
char c = getchar();
while(c < '0' || c > '9') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - 48,c = getchar();
return x;
}
struct edge{
int v,w,nxt;
edge(){};
}e[M];
struct Edge{
int u, v, w;
Edge(int u,int v,int w):u(u),v(v),w(w){};
Edge(){};
};
vector<Edge> other;
int head[N],EN;
int pa[N];
int Find(int x){
return pa[x] == x?x:pa[x] = Find(pa[x]);
}
int A[100010],B[100010],ca,cb;
void init(){
ca = cb = EN = 0;
memset(head,-1,sizeof(head));
other.clear();
for(int i = 1;i <= n;i++) pa[i] = i;
}
void add(int u,int v,int w){
e[EN].v = v,e[EN].w = w,e[EN].nxt = head[u];
head[u] = EN++;
}
bool dfs(int u,int f,int ed){
if(u == ed) return true;
for(int i = head[u];~i;i = e[i].nxt){
if(i == f) continue;
if(dfs(e[i].v,i ^ 1,ed)){
B[cb++] = e[i].w;
return true;
}
}
return false;
}
bool cmp(int x,int y){
return x > y;
}
void Merge(){
if(ca > cb) swap(ca,cb),swap(A,B);
priority_queue<P> q;
for(int i = 0;i < ca;i++) q.push(P(A[i]+B[0],0));
int siz = min(K, ca * cb);
ca = 0;
for(int i = 0;i < siz;i++){
P cur = q.top();q.pop();
A[ca++] = cur.first;
if(cur.second + 1 < cb) q.push(P(cur.first - B[cur.second] + B[cur.second+1],cur.second + 1));
}
}
int main(){
int cas = 1, u, v, w;
while(scanf("%d%d",&n,&m)==2){
init();
int total = 0;
for(int i = 0;i < m;i++){
u = read(),v = read(),w = read();
if(Find(u) != Find(v)){
add(u, v, w);
add(v, u, w);
pa[Find(u)] = Find(v);
}else {
other.push_back(Edge(u,v,w));
}
total += w;
}
K = read();
int first = 1;
for(auto E:other){
dfs(E.u,-1,E.v);
B[cb++] = E.w;
sort(B, B + cb,cmp);
if(first) first = 0,swap(A,B),swap(ca,cb);
else Merge();
cb = 0;
}
LL ans = 0;
for(int i = 0;i < ca;i++) {
ans = (ans + 1LL * (i + 1) * (total - A[i]))%mod;
}
if(!ca) ans = total;
printf("Case #%d: %lld\n",cas++,ans);
}
return 0;
}