和题解大致相同的思路

/*HDU 6041 - I Curse Myself [ 图论,找环,最大k和 ]  |  2017 Multi-University Training Contest 1题意：	给出一个仙人掌图，求最小的k棵生成树	N <= 1000, M <= 2000, K <= 1e5分析：	将问题转化为从每个环中选出一条边，求最大的k个和	首先找环，随便怎么找，比如 在保证每条边只走一次的情况下遍历到祖先节点就说明有环，记录一下前驱就能找出来	然后是每个环两两合并，此时相当于两个vector，res.size() = k，cir[i].size() = Mi, ∑mi = M	由于 M<=2000,k <= 1e5，故选择在堆中的元素是cir[i]中的元素	这样就能保证复杂度为 O( ∑K*log(mi) ) = O( K*log(∏mi) ) <= O(K*M)编码时长: INF(-8)*/#include 
     
      using namespace std;#define LL long longconst LL MOD = 1LL<<32;const int N = 1005;struct Edge {    int to, next, w;    bool vis;}edge[N<<2];int head[N], tot;void init() {    memset(head, -1, sizeof(head));    tot = 0;}void addedge(int u, int v, int w) {    edge[tot].to = v; edge[tot].next = head[u];    edge[tot].vis = 0; edge[tot].w = w;    head[u] = tot++;}int n, m, block;vector
      
        cir[N];bool vis[N];int f[N], g[N];//父节点和连着的边void dfs(int u){    for (int i = head[u]; i != -1; i = edge[i].next)    {        int v = edge[i].to;        if (edge[i].vis) continue;        edge[i].vis = 1;        edge[i^1].vis = 1;        if (vis[v])        {            ++block;            int t = u;            do{                cir[block].push_back(edge[g[t]].w);                t = f[t];            }while (t != v);            cir[block].push_back(edge[i].w);        }        else        {            vis[v] = 1, f[v] = u, g[v] = i;            dfs(v);        }    }}void find_cir(){    for (int i = 0; i < N; i++) cir[i].clear();    memset(vis, 0, sizeof(vis));    block = 0;    vis[1] = 1;    dfs(1);}struct Node {    int x, id;    bool operator < (const Node& b) const {//大的先出去        return x < b.x;    }};priority_queue
       
         Q;vector
        
          res, tmp;void solve(int k){    res.clear();    res.push_back(0);    for (int i = 1; i <= block; ++i)    {        while (!Q.empty()) Q.pop();        tmp.clear();        for (auto& x : cir[i])            Q.push(Node{x+res[0], 0});        while (tmp.size() < k && !Q.empty())        {            auto p = Q.top(); Q.pop();            tmp.push_back(p.x);            if (p.id+1 < res.size())            {                ++p.id;                p.x += res[p.id] - res[p.id-1];                Q.push(p);            }        }        res.clear();        for (auto& x : tmp) res.push_back(x);    }}int main(){    int tt = 0, u, v, w, k;    while (~scanf("%d%d", &n, &m))    {        init();        LL sum = 0, ans = 0;        for (int i = 1; i <= m; i++)        {            scanf("%d%d%d", &u, &v, &w);            sum += w;            addedge(u, v, w); addedge(v, u, w);        }        find_cir();        scanf("%d", &k);        solve(k);        for (int i = 0; i < res.size(); i++)            ans += (i+1) * ( (sum-res[i])) % MOD;        printf("Case #%d: %lld\n", ++tt, ans%MOD);    }}
        
       
      
     

　　

限制第k小的大小后，满足这个限制的答案的数量具有单调性，故还可以二分第k小 暴力DFS+剪枝 验证，就是代码不算好写

#include 
     
      using namespace std;#define LL long longconst int N = 1005;const LL MOD = 1LL<<32;struct Edge {    int to, next, w;    bool vis;}edge[N<<2];int head[N], tot;void init() {    memset(head, -1, sizeof(head));    tot = 0;}void addedge(int u, int v, int w) {    edge[tot].w = w; edge[tot].to = v; edge[tot].next = head[u];    edge[tot].vis = 0;    head[u] = tot++;}int block;vector
      
        cir[N];int f[N], g[N], vis[N];void dfs(int u){    for (int i = head[u]; ~i; i = edge[i].next)    {        if (edge[i].vis) continue;        edge[i].vis = 1;        edge[i^1].vis = 1;        int v = edge[i].to;        if (vis[v])        {            ++block;            int t = u;            do {                cir[block].push_back(edge[g[t]].w);                t = f[t];            }while (t != v);            cir[block].push_back(edge[i].w);        }        else        {            vis[v] = 1;            f[v] = u, g[v] = i;            dfs(v);        }    }}void find_cir(){    for (int i = 0; i < N; i++) cir[i].clear();    memset(vis, 0, sizeof(vis));    block = 0;    vis[1] = 1;    dfs(1);}bool cmp (const int &x, const int &y) {    return x > y;}int n, m, k, num;LL mid, res[100005];void dfs(int i, LL sum){    if (num > k) return;    if (sum > mid) return;    if (i == block+1)    {        res[++num] = sum; return;    }    for (auto& x : cir[i])    {        if (sum + x > mid) break;        dfs(i+1, sum+x);    }}LL BinaryFind(LL l, LL r){    while (l <= r)    {        mid = (l+r)>>1;        num = 0;        dfs(1, 0);        if (num >= k) r = mid-1;        else l = mid+1;    }    return l;}int main(){    int t = 0, x, y, z;    while (~scanf("%d%d", &n, &m))    {        init();        LL base = 0, ans = 0;        for (int i = 1; i <= m; i++)        {            scanf("%d%d%d", &x, &y, &z);            addedge(x, y, z), addedge(y, x, z);            base += z;        }        find_cir();        scanf("%d", &k);        printf("Case #%d: ", ++t);        if (block == 0)        {            printf("%lld\n", base%MOD); continue;        }        for (int i = 1; i <= block; i++)        {            sort(cir[i].begin(), cir[i].end(), cmp);            base -= cir[i][0];            for (int j = 1; j < cir[i].size(); j++)                cir[i][j] = cir[i][0] - cir[i][j];            cir[i][0] = 0;        }        int Max = 1;        for (int i = 1; i <= block && Max < k; i++)            Max *= cir[i].size();        if (k > Max)        {            k = Max;            mid = 2e9;            num = 0;            dfs(1, 0);        }        else        {            mid = BinaryFind(1, 2e9);            mid--;            num = 0;            dfs(1, 0);            for (int i = num+1; i <= k; i++) res[i] = mid+1;        }        sort(res+1, res+k+1);        for (int i = 1; i <= k; i++)            ans += i * (base+res[i]) % MOD;        printf("%lld\n", ans% MOD);    }}