Chương trình C++ tìm giảm điểm tối đa khi xóa cạnh giữ đồ thị liên thông

Mô tả bài toán

Cho đồ thị vô hướng có trọng số (có thể âm). Điểm của đồ thị = tổng trọng số cạnh. Xóa cạnh sao cho đồ thị vẫn liên thông và điểm giảm nhiều nhất (tức là xóa các cạnh dương không cần thiết cho liên thông). Tìm giá trị giảm tối đa.

Ví dụ

n=5,m=6, edges={{2,{1,2}},{2,{1,3}},{1,{2,3}},{3,{2,4}},{2,{2,5}},{1,{3,5}}}. Đầu ra: 4 (xóa cạnh (1,2) và (2,5)).

Thuật toán (Kruskal biến đổi)

1. Sắp xếp cạnh theo trọng số tăng dần.
2. DSU (Union-Find) quản lý thành phần liên thông.
3. Duyệt cạnh: nếu 2 đỉnh đã cùng thành phần → cạnh tạo chu trình. Nếu trọng số ≥ 0 → cộng vào kết quả (có thể xóa).
4. Nếu chưa cùng thành phần: nếu đã liên thông toàn bộ (cnum==1) và trọng số ≥ 0 → cộng vào kết quả; ngược lại union.

Đoạn mã C++

#include <bits/stdc++.h>
using namespace std;

int cnum=0, par[100], dim[100];
void make(int v){ par[v]=v; dim[v]=1; }
int find(int v){ return par[v]==v?v:par[v]=find(par[v]); }
void unify(int a,int b){
    a=find(a); b=find(b);
    if(a!=b){
        cnum--;
        if(dim[a]>dim[b]) swap(a,b);
        par[a]=b; dim[b]+=dim[a];
    }
}

int solve(int n,int m,vector<pair<int,pair<int,int>>> edges){
    cnum=n;
    sort(edges.begin(),edges.end());
    for(int i=1;i<=n;i++) make(i);
    int res=0;
    for(auto &e:edges){
        int a=e.second.first, b=e.second.second, w=e.first;
        if(find(a)==find(b)){
            if(w>=0) res+=w;
            continue;
        }
        if(cnum==1){
            if(w>=0) res+=w;
        }else unify(a,b);
    }
    return res;
}

int main(){
    int n=5,m=6;
    vector<pair<int,pair<int,int>>> edges=
        {{2,{1,2}},{2,{1,3}},{1,{2,3}},{3,{2,4}},{2,{2,5}},{1,{3,5}}};
    cout << solve(n,m,edges);
    return 0;
}

Đầu vào / Đầu ra

Input: 5, 6, {{2,{1,2}},{2,{1,3}},{1,{2,3}},{3,{2,4}},{2,{2,5}},{1,{3,5}}}

Output: 4