code bài D MST
//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