评测记录

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<string>
#include<cstring>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;++i)
using namespace std;
const int INF=0x1fffffff;
struct edge
{
    int x,y,weight,id;
    edge(int x_,int y_,int weight_,int id_):
        x(x_),y(y_),weight(weight_),id(id_){}
};
int n,m,k,bin[100001],s[100001];
vector<edge> v,ans;
bool cmp1(edge a,edge b)
{
    return a.weight<b.weight;
}
bool cmp2(edge a,edge b)
{
    return a.weight>b.weight;
}
int anc(int k)
{
    if(!bin[k])
        return k;
    return bin[k]=anc(bin[k]);
}
inline void link(int a,int b)
{
    a=anc(a);
    b=anc(b);
    if(a!=b)
    {
        if(s[a]<s[b])
        {
            bin[a]=b;
            s[b]+=s[a];
        }
        else
        {
            bin[b]=a;
            s[a]+=s[b];
        }
    }
}
inline void kruskal_1()
{
    int cnt=0;
    for(vector<edge>::iterator it=v.begin();it!=v.end();++it)
    {
        int u=it->x,v=it->y;
        if(anc(u)!=anc(v))
        {
            link(u,v);
            ans.push_back(edge(u,v,it->weight,it->id));
            ++cnt;
        }
        if(cnt==k)
            return;
    }
    if(cnt<k)
    {
        cout<<"no solution\n";
        exit(0);
    }
}
inline void kruskal_2()
{
    int cnt=0;
    for(vector<edge>::iterator it=v.begin();it!=v.end();++it)
    {
        if(it->weight==0)
            break;
        int u=it->x,v=it->y;
        if(anc(u)!=anc(v))
        {
            link(u,v);
            ++cnt;
            ans.push_back(edge(u,v,it->weight,it->id));
        }
    }
    if(cnt<n-k-1)
    {
        cout<<"no solution\n";
        exit(0);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m>>k;
    int tot=0;
    For(i,1,m)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(!c)
            ++tot;
        v.push_back(edge(a,b,c,i));
    }
    if(tot<k)
    {
        cout<<"no solution\n";
        return 0;
    }
    sort(v.begin(),v.end(),cmp1);
    kruskal_1();
    sort(v.begin(),v.end(),cmp2);
    kruskal_2();
    for(vector<edge>::iterator it=ans.begin();it!=ans.end();++it)
        cout<<it->x<<" "<<it->y<<" "<<it->weight<<endl;
    return 0;
}

手动@大佬

@vercont

@心之泪殇