code bài D MST

 avatar
unknown
c_cpp
17 days ago
2.4 kB
3
Indexable
//code sieu trau bo(EVEN THAN A bitcoin miner)
 
 
#include<bits/stdc++.h>
using namespace std;
 
#define maxn 502
#define maxm 50004
 
int n,m,minn;
int goc[maxn];
int laygoc(int x){
    if (goc[x]==-1) return x;
    return (goc[x]=laygoc(goc[x]));
}
 
bool check_lienthong(){
    int goc_chung=laygoc(1);
    for (int i=1;i<=n;i++)
        if (laygoc(i)!=goc_chung) return 0;
    return 1;
}
 
struct canhj{
    int tu,den,dodai;
    bool operator==(canhj b){
        return (tu==b.tu&&den==b.den&&dodai==b.dodai);
    }
    bool operator<(canhj b){
        return dodai<b.dodai;
}
};
 
vector<canhj> giulai;
canhj canhj_0=canhj{-1,-1,-1};
 
void sx_chen(canhj x){
    for (int i=giulai.size()-1;i>=0;i--){
        if (giulai[i]<x) {
            giulai.insert(giulai.begin()+i+1,x);
            return;
        }
    }
    giulai.insert(giulai.begin(),x);
}
 
int kruskal(){
    //dam bao giulai da sap xep
    fill(goc,goc+maxn,-1);
    int res=0;
    for (canhj& i:giulai){
        int gtu=laygoc(i.tu),gden=laygoc(i.den);
        if (gtu==gden) {
            //this i should be removed
            i=canhj{-1,-1,-1}; //this mean nothing
            continue;
        };
        goc[gtu]=gden;
        res+=i.dodai;
    }
    if (check_lienthong()) {
        //compact
        int bias=0;
        for (int i=0;i<giulai.size();i++){
            if (giulai[i]==canhj_0){
                bias++;
            }
            else{
                giulai[i-bias]=giulai[i];
            }
        }
        giulai.erase(giulai.end()-bias,giulai.end());
        return res;
    }
    return INT_MAX;
}
 
int main(){
    fill(goc,goc+maxn,-1);
    giulai.reserve(maxn);
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    if (fopen("i.txt","r")){
        freopen("i.txt","r",stdin);
        freopen("o.txt","w",stdout);
    }
 
    cin>>n>>m;
    bool fuck=0;
    while(m--){
        canhj c{};
        cin>>c.tu>>c.den>>c.dodai;
        int gtu=laygoc(c.tu),gden=laygoc(c.den);
        if (gtu!=gden) goc[gtu]=gden;
        if (check_lienthong()){
            if (fuck==0)sort(giulai.begin(),giulai.end());
            fuck=1;
            sx_chen(c);
            cout<<kruskal();
        }
        else {
            giulai.push_back(c);
            cout<<-1;
        }
        cout<<'\n';
    }
}
Leave a Comment