(第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
    
     #define LL long long#define P pair
     
      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
      
        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
       
 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;}