【题解】luogu-P2872-USACO07DEC-道路建设Building-Roads

为什么这么多恶意评分啊qwq，这题明明很水的说
好那么我们首先来看一下题意，题目让我们先找一边把需要建的一等公路先建出来（等级高就是可以为所欲为，然后再把剩余需要建的二等公路建出来
其实我们可以用一个结构体，里面开两个dis值，分别代表一等和二等，手打两个cmp，排序之后疯狂找就好了qwq
但是注意，由于题目让我们输出的是方案和最大值，而不是价钱，所以我们在跑kruskal的时候要注意把每一步的过程用一个数组保存下来，这样最后再筛一遍就能直接输出啦qwq
剩下的一些过程放在代码里了qwq

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>

using namespace std;

struct Edge1{
    int x,y,dis1,dis2,num;//dis1表示一等，dis2表示二等
}a1[100001];

int father[100001],k,m,n,maxx=0,k1=0,f[100001][2],m1=0; //f[1]表示建一等公路的序号f[0]表示二等的序号，结构体的num即可以表示

bool cmp1(Edge1 x,Edge1 y){return x.dis1<y.dis1;}//一等排序

bool cmp2(Edge1 x,Edge1 y){return x.dis2<y.dis2;}//二等排序

int find(int x)//找爹
{
    if(father[x]!=x) father[x]=find(father[x]);
    return father[x];
}

void unionn(int x,int y)//咱俩合起来了qwq！！
{
    x=find(x),y=find(y);
    father[x]=y;
}

int main()
{
    scanf("%d%d%d",&n,&k,&m);
    m--;//先减一好计算（其实是我容易忘
    for(int i=1; i<=n; i++) father[i]=i;//初始化
    for(int i=1; i<=m; i++)
    {
        int x,y,c1,c2;
        scanf("%d%d%d%d",&x,&y,&c1,&c2);
        a1[i].x=x; 
        a1[i].y=y;
        a1[i].dis1=c1;a1[i].dis2=c2;
        a1[i].num=i;//一定把序号存上
    }
    sort(a1+1,a1+m+1,cmp1);//一等先来
    for(int i=1; i<=m; i++)//标准最小生成树
    {
        if(find(a1[i].x)!=find(a1[i].y))
        {
            unionn(a1[i].x,a1[i].y);
            k1++;
            f[a1[i].num][1]=1; //保存此时你选择的边序号
        }
        if(k1==k)
        {
            maxx=a1[i].dis1;
            break;
        }
    }
    k1=0;
    sort(a1+1,a1+m+1,cmp2);
    for(int i=1; i<=m; i++)//二等再跑一遍最小生成树
    {
        if(find(a1[i].x)!=find(a1[i].y))
        {
            unionn(a1[i].x,a1[i].y);
            k1++;
            f[a1[i].num][0]=1;
        }
        if(k1==n-k-1)
        {
            maxx=max(maxx,a1[i].dis2);
            break;
        }
    }
    printf("%d\n",maxx);
    for(int i=1; i<=m; i++) 
        if(f[i][1]!=0) printf("%d 1\n",i);
        else if(f[i][0]!=0) printf("%d 2\n",i);
}