โปรแกรม C++ หาคะแนนสูงสุดที่ลดได้จากกราฟโดยคงความเชื่อมต่อ

กำหนดกราฟไม่มีทิศทาง มีน้ำหนัก n จุดยอด m เส้นขอบ คะแนนกราฟ = ผลรวมน้ำหนักขอบทั้งหมด น้ำหนักอาจเป็นลบ (ลบออกคะแนนจะเพิ่ม) ต้องลบขอบบางส่วนเพื่อทำให้คะแนนน้อยที่สุด (คือลดคะแนนมากที่สุด) แต่กราฟต้องยังคงเชื่อมต่อ ต้องการหาจำนวนคะแนนที่ลดได้สูงสุด

ตัวอย่าง: n=5,m=6, edges={{2,{1,2}},{2,{1,3}},{1,{2,3}},{3,{2,4}},{2,{2,5}},{1,{3,5}}} ผลลัพธ์: 4 (ลบขอบ (1,2) และ (2,5) น้ำหนักรวม 4 กราฟยังเชื่อมต่อ)

ขั้นตอนการแก้ปัญหา (Kruskal แบบปรับเปลี่ยน / Union-Find)

1. Union-Find (make, find, unify) นับคอมโพเนนต์ cnum
2. เรียงขอบตามน้ำหนักน้อยไปมาก
3. เริ่มต้น make(i) ทุกจุดยอด cnum = n
4. วนขอบที่เรียงแล้ว:
   • ถ้าจุดยอดอยู่คอมโพเนนต์เดียวกัน (find(a)==find(b)) และน้ำหนัก ≥ 0 → บวกเข้าผลลัพธ์ (ลบขอบนี้ได้)
   • ถ้า cnum == 1 (เชื่อมต่อครบแล้ว) และน้ำหนัก ≥ 0 → บวกเข้าผลลัพธ์
   • มิฉะนั้น unify(a,b) (เก็บขอบนี้ไว้เพื่อความเชื่อมต่อ)
5. คืนค่าผลลัพธ์

ตัวอย่างโค้ด 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 &edge : edges) {
        int a = edge.second.first, b = edge.second.second, w = edge.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;
}

อินพุต / เอาต์พุต

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

Output: 4