[At] E - Destruction 最小生成树(负权)

前言

传送门 : https://atcoder.jp/contests/abc218/tasks/abc218_e

思路

看完题目发现就是跑一个最小生成树

但是有负权,不能直接跑

因此我们不如反过来想,将负权边加入到集合当中

尽可能的少加入正权边,这样又可以安心的跑最小生成树了

CODE

#include 
using namespace std;
using ll =long long;
const int INF = 0x3f3f3f3f;
const int N = 2e5+10;
const int M = 4e5+10;
int p[N];
int n,m;

struct Edge
{
    int a, b, w;
    bool operatorm;
    ll sum = 0;
    
    for(int i=1;ia>>b>>k;
        edges[i]={a,b,k};
        sum+=k;
    }
    cout