崩溃,错了,又不知道怎么加二分......
查看原帖
崩溃,错了,又不知道怎么加二分......
1325916
VelvetChords楼主2024/4/23 23:10

哪位大佬帮帮我改一下代码,崩溃了......

#include<bits/stdc++.h>
using namespace std; 
struct SQS 
{
    long long u,v,w;
};
struct bqz 
{
    vector<long long> p;
    bqz(long long n) 
    {
        p.resize(n);
        for(int i=0;i<n;i++)
            p[i]=i;
    }
    int find(long long u) 
    {
        if(p[u]!=u)
            p[u]=find(p[u]);
        return p[u];
    }
    void mg(long long u, long long v) 
    {
        p[find(u)]=find(v);
    }
};
bool bj(const SQS& a,const SQS& b)
{
    return a.w<b.w;
}
vector<SQS> kruskal(vector<SQS>& ss,long long n,long long k) 
{
    sort(ss.begin(),ss.end(),bj);
    bqz uf(n);
    vector<SQS> re;
    long long sum=0;
    for(vector<SQS>::iterator it=ss.begin();it!=ss.end();it++) 
    {
        SQS&s=*it;
        if(uf.find(s.u)!=uf.find(s.v)) 
        {
            uf.mg(s.u,s.v);
            re.push_back(s);
            sum++;
        }
    }
    if (sum<n-1||sum>k)
        return vector<SQS>();
    return re;
}
long long n,m,k;
int main() 
{    
    cin>>n>>m>>k;
    vector<SQS> ss(m);
    for(long long i=0;i<m;i++) 
    {
        cin>>ss[i].u>>ss[i].v>>ss[i].w;
        ss[i].u--;
        ss[i].v--;
    }
    vector<SQS> re=kruskal(ss,n,k);
    if(re.empty()) cout<<"Impossible";       
    else 
    {
        long long tans=0;
        for (vector<SQS>::iterator it=re.begin();it!=re.end();it++) 
            tans+=it->w;
        cout<<tans;
    }
    return 0;
}
2024/4/23 23:10
加载中...