< hamamuさんのAI生成コード置き場

クラスカル法

日時はサーバーが記録したものです。更新すると更新日時が変わるので、不都合がある場合は新しく投稿してください。

//generated by GPT-5.4?, modified by hamamu
template<class T,class S=typename tuple_element<2,T>::type>
struct kruskal{
    unionfind<> uft;
    S sumCost=S(0); //総コスト
    vector<T> usedEdges;   //使用した辺
    vector<T> unusedEdges; //使用しなかった辺
    kruskal(ll N,vector<T> uvc,bool isMin=true):uft(N){
        sort(uvc.begin(),uvc.end(),
            [](const T&x,const T&y){return get<2>(x)<get<2>(y); });
        if (!isMin)
            reverse(uvc.begin(),uvc.end());
        for (auto &&edge: uvc){
            ll   v=get<0>(edge);
            ll   u=get<1>(edge);
            S cost=get<2>(edge);
            if (uft.merge(u,v))
                usedEdges.push_back(edge), sumCost+=cost;
            else
                unusedEdges.push_back(edge);
        }
    }
    S sumcost()const{ return sumCost; }
    vector<T> &usededges(){ return usedEdges; }
    vector<T> &unusededges(){ return unusedEdges; }
    unionfind<> &Uft(){ return uft; }
};
/*
kruskal kr(N,uvc);       //最小全域木
kruskal kr(N,uvc,false); //最大全域木 ＜動作確認未＞
.   頂点数┘ └辺<u,v,cost(,etc,…)>のvector

ll c=kr.sumcost();                //総コスト
vtll   &useduvc=kr.usededges();   //使った辺 ＜動作確認未＞
vtll &unuseduvc=kr.unusededges(); //使わなかった辺 ＜動作確認未＞
auto &uft=kr.Uft();               //unionfind
*/