P2323 公路修建问题

题面:https://www.luogu.org/problemnew/show/P2323

本题首先按照c1排序，选出前k条边，然后按照c2排序，选出剩下n-1-k条边。
找其中的最大花费即为答案。

Code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=20005;
int n,m,k,f[N],s[N],ans,cnt;
struct Node{
    int u,r,c1,c2,num;
}d[N];
bool cmp1(Node a,Node b){
    return a.c1<b.c1;
}
bool cmp2(Node a,Node b){
    return a.c2<b.c2;
}
int find(int x){
    if(x!=f[x]){
		f[x]=find(f[x]);
	}
    return f[x];
}
int main(){
    cin>>n>>k>>m;
    m--;
    for(int i=1;i<=n;i++){
		f[i]=i;
	}
    for(int i=1;i<=m;i++){
        cin>>d[i].u>>d[i].r>>d[i].c1>>d[i].c2;
        d[i].num=i;
    }
    sort(d+1,d+1+m,cmp1);
    for(int i=1;i<=m;i++){
        int x,y;
        x=find(d[i].u);
        y=find(d[i].r);
        if(x!=y){
            f[y]=x;
            ans=max(ans,d[i].c1);
            s[d[i].num]=1;
            cnt++;
        }
        if(cnt==k){
            k=i;
            break;
        }
    }
    sort(d+k+1,d+1+m,cmp2);
    for(int i=k+1;i<=m;i++){
        int x,y;
        x=find(d[i].u);
        y=find(d[i].r);
        if(x!=y){
            f[y]=x;
            ans=max(ans,d[i].c2);
            s[d[i].num]=2;
        }
    }
    cout<<ans<<endl;
    for(int i=1;i<=m;i++){
        if(s[i]>=1){
			cout<<i<<" "<<s[i]<<endl;
		}
    }
    return 0;
}