最小生成树、kruskai算法

题意：

废话：做了些题单的题后，我发现题目考察点基本上围绕着 建图、算法本身理解、dp 三点展开。
本题考察的是对kruskai算法的理解

分析：

我们首先抓住重要信息：公路1是一定比公路2开销大的！至少要有k条公路1.
那么很明显我们就只铺设k条公路1好了，剩下的都铺设公路2！！这是个贪心。

那么问题来了，我们选取那些路铺设公路1呢？

下面想想kruskai算法的原理：
kruskai算法是求最小路的算法。
假设我们有两个由点组成的树，我们要把这两个树连接在一起以形成一个树。我们只能依靠这两个树他们中节点相互链接的路径。kruskai指出，链接最短路是最优的。这样我们能获得最小生成树
那么我们在kruskai设想的情境下展开思考：
两个数，我们需要选择一条边链接他们。待选边：
[e1,e2,e3,e4......] 如何选择huishi最后的最大边的值尽量小呢？
贪心策略：选最小边！没错！和kruskai算法的贪心策略完全一样！
证明：我们已知在边集中选择一条，然后其他的边都再也不可能被选到了！
那么为了保证最大边的值最小我们何不在此选择最小边呢？

由此，我们知道了那k条公路1的边该怎么选了。
我们就按照kruskai算法，即刚才的贪心思路选出k条边！我可保证这k条公路1的边对最后结果影响是最小的。
然后的剩下在使用kruskai算法，只不过都选公路2.

代码如下：

#include<iostream>
#include<algorithm>
using namespace std;
const int max_n = 1e4 + 100;
const int inf = 2e9;
const int max_m = 2e4 + 100;
struct edge { int u, v, cost1, cost2; };
edge E[max_m];
int n, k, m;
int ans = -1;

int par[max_n];
int rak[max_n];
bool cmp1(edge&, edge&);
bool cmp2(edge&, edge&);
void init();
int find(int x);
bool same(int x, int y);
bool merge(int x, int y);
void kruskai1();
void kruskai2();

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> k >> m;init();
    for (int i = 1;i < m;i++)cin >> E[i].u >> E[i].v >> E[i].cost1 >> E[i].cost2;
    kruskai1();kruskai2();cout << ans << endl;
}

bool cmp1(edge& e1, edge& e2) { return e1.cost1 < e2.cost1; }
bool cmp2(edge& e1, edge& e2) { return e1.cost2 < e2.cost2; }
void init() {
    for (int i = 1;i <= n;i++)par[i] = i;
    fill(rak, rak + 1 + n, 0);
}
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
bool same(int x, int y) { return find(x) == find(y); }
bool merge(int x, int y) {
    x = find(x);y = find(y);
    if (x == y)return false;
    if (rak[x] > rak[y])par[y] = x;
    else if (rak[x] < rak[y])par[x] = y;
    else par[y] = x, rak[x]++;
    return true;
}
void kruskai1() {
    sort(E + 1, E + m, cmp1);
    for (int i = 1;i < m && k;i++) {
        if (merge(E[i].u, E[i].v))
            ans = max(ans, E[i].cost1), k--;
    }
}
void kruskai2() {
    sort(E + 1, E + m, cmp2);
    for (int i = 1;i < m;i++) {
        if (merge(E[i].u, E[i].v))
            ans = max(ans, E[i].cost2);
    }
}