无环最大代价问题求解求助：现有代码无法正确解决问题

给定带正边权的无向图，需选择一个无环的边子集，使得边权总和最大。
输入包含多个图，每个图的定义为：顶点数n、边数m，以及m个三元组x,y,c，表示顶点x与y之间存在一条权值为c的边。顶点编号从0到n-1，约束条件为1 ≤ n ≤ 10⁴，0 ≤ m ≤ 5n，1 ≤ c ≤ 10⁵，图中允许多重边和自环。

#include <iostream>
#include <vector>

using namespace std;
using P = pair<int,int>;
using VE = vector<int>;
using VP = vector<P>;
using VVE = vector<VP>;

int n,m;
VVE G;
VE cost; 
VE vist; 
VE pare; 

int maxim(int x){
   if(cost[x] != -1) return cost[x];
   cost[x] = 0; 
   for(P y: G[x]){
      if(cost[x] <= y.second + maxim(y.first)){
        cost[x] = y.second + maxim(y.first);
      }
   }
 return cost[x];
}

int main() {
  while(cin >> n >> m){
     G = VVE(n);
     cost = VE(n,-1);
     pare = VE(n,-1);
     for(int i = 0; i < m; ++i){
         int x,y,c; cin >> x >> y >> c; 
         G[x].push_back(P(y,c));
         G[y].push_back(P(x,c));
     }
     int mx = -1; 
     for(int i = 0; i < n; ++i){
         if(mx <= maxim(i)){
             mx = maxim(i);
         }
     }
     cout << mx << endl; 
  }
}

你的代码核心逻辑完全错误，把问题当成了求图中的最长路径，但实际要解决的是最大权无环边子集——这个问题等价于求最大生成森林：无环边子集本质是森林，而最大权的无环边子集就是所有连通分量的最大生成树的边权总和（选最大生成树能保证边权总和最大且无环，添加任何边都会形成环，去掉任何边都会减少总和）。

你的代码存在的问题 #

1. 逻辑偏差：最长路径和最大无环边子集是完全不同的问题，前者是找单条路径的最大权值和，后者是选尽可能多的大权重边且不形成环，目标完全不一致。
2. 递归风险：无向图存在环时，递归会陷入循环调用（比如x和y互连，maxim(x)调用maxim(y)，maxim(y)又调用maxim(x)）；对于n=1e4的场景，递归深度会远超程序栈默认大小，直接导致崩溃。
3. 自环处理错误：自环本身就是环，不能加入无环边子集，但你的代码会将其权值计入结果，导致答案错误。

正确解法：Kruskal算法实现最大生成森林 #

Kruskal算法适合处理这类问题，步骤如下：

1. 把所有边按权值从大到小排序。
2. 用并查集（DSU）判断添加当前边是否会形成环：若边的两个顶点不在同一集合，则添加这条边并合并集合；否则跳过。
3. 累加所有选中边的权值，总和即为答案。
4. 直接跳过自环，因为自环不符合无环要求。

修正后的代码 #

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int u, v, c;
    Edge(int u_, int v_, int c_) : u(u_), v(v_), c(c_) {}
    // 按权值降序排序
    bool operator<(const Edge& other) const {
        return c > other.c;
    }
};

vector<int> parent;
vector<int> rank_;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    if (rank_[x] < rank_[y]) {
        parent[x] = y;
    } else {
        parent[y] = x;
        if (rank_[x] == rank_[y]) {
            rank_[x]++;
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m;
    while (cin >> n >> m) {
        vector<Edge> edges;
        edges.reserve(m);
        for (int i = 0; i < m; ++i) {
            int x, y, c;
            cin >> x >> y >> c;
            // 跳过自环
            if (x == y) continue;
            edges.emplace_back(x, y, c);
        }
        
        sort(edges.begin(), edges.end());
        
        parent.resize(n);
        rank_.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
        
        long long total = 0;
        for (const Edge& e : edges) {
            if (unite(e.u, e.v)) {
                total += e.c;
            }
        }
        
        cout << total << '\n';
    }
    
    return 0;
}

代码说明 #

• 用ios::sync_with_stdio(false);和cin.tie(nullptr);加速输入输出，适配大规模数据。
• 并查集使用路径压缩和按秩合并，保证操作时间复杂度接近O(α(n))（α是阿克曼函数的反函数，增长极慢）。
• 直接跳过自环，避免引入环结构。
• 边按权值降序排序，优先选择大权重边，保证总和最大。

内容的提问来源于stack exchange，提问作者B.Casals