2022/7/ 20 训练记录

算法训练 Kruskal算法 P2323 [HNOI2006]公路修建问题

思路：复习了一遍kruskal算法。本题较为复杂，但拆解下来算法中都是常规操作。 1.对一级公路进行排序，跑一遍kurskal算法，当一级公路数量达到k时，则返回退出，记录最大的公路数值； 2.同样，对二级公路排序，再重新写一个kruskal算法，当数量达到n-1-k则退出循环，记录二级公路最大数值； 3.这种做法认真想来是存在问题的，如果k条一级公路选定后数值小于二级公路最大数值，那么可以再继续选1级公路，二级公路则选前面一条公路数值，进行比较，判断出最小；

#include 
//#define int long long
#define endl '\n'

using namespace std;
const int N=1e5+100;
int n,k,m,f[N],g,minn;
bool vis[N];
struct node
{
    int a,b,c1,c2,id;
}e[N];
struct Ans
{
    int p,q;
}ans[N];
bool cmp1(node n1,node n2)
{
    return n1.c1>m;
    m-=1;
    for(int i=1;ie[i].a>>e[i].b>>e[i].c1>>e[i].c2;
        e[i].id=i;
    }
    sort(e+1,e+m+1,cmp1);
    kruskal1();
    sort(e+1,e+m+1,cmp2);
    kruskal2();
    cout