经典算法改一改, 就不会做了…

懵逼的 题目

GG

扯淡的 题解

和昊哥yy了半天, 无果, 于是抄题解

感觉思路挺有意思的…

  • 二分一个值$k$, 然后把所有的白边的边权都加上$k$
  • kuskal, 记录生成树中白边的条数$re$
    • $re > need$: 把$k$变大
    • $re < need$: 把$k$变小
    • $re = need$: 这时的生成树权值就是答案

因为给白边加的都是一个数, 所以白边的相对大小没变, 选出来的还是最小的那些白边, 所以答案是正确的…

沙茶的 代码

实现的时候注意可能白边黑边的权值一样, 所以实际写起来是下面这样…

/**************************************************************
    Problem: 2654
    User: Cansult
    Language: C++
    Result: Accepted
    Time:7116 ms
    Memory:4812 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (50000 + 5)
#define MAXM (100000 + 5)
#define INF (0x7fffffff)
#define int long long
#define pii pair<int, int>
#define mkp(a, b) make_pair(a, b)
using namespace std;
struct edg
{
    int from, to, cost, ki;
}b[MAXM];
int fa[MAXN], n, m, need, nw;
int find(int x)
{ return (x == fa[x] ? x : (fa[x] = find(fa[x]))); }
void uni(int x, int y)
{ fa[find(x)] = find(y); }
bool cmp(edg x, edg y)
{
    if (x.cost != y.cost)
        return x.cost < y.cost;
    else
        return x.ki < y.ki;
}
pii kruskal()
{
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    sort(b + 1, b + m + 1, cmp);
    int cntb = 0;
    pii re = mkp(0, 0);
    for (int i = 1; i <= m; i++)
        if (find(b[i].from) != find(b[i].to))
        {
            if (re.first >= need && !b[i].ki)
            {
                re.first = need + 1;
                continue;
            }
            ++cntb;
            re.first += 1 - b[i].ki;
            re.second += b[i].cost;
            uni(b[i].from, b[i].to);
            if (cntb == n - 1)
                break;
        }
    return re;
}
int ef()
{
    int le = -200, ri = 200, last = 0, re = INF;
    while (le < ri)
    {
        int mi = (le + ri) >> 1;
        for (int i = 1; i <= m; i++)
            if (!b[i].ki)
                b[i].cost += mi - last;
        pii dq = kruskal();
        if (dq.first >= need)
        {
            re = min(re, dq.second - nw * mi);
            le = mi + 1;
        }
        else
            ri = mi;
        last = mi;
    }
    return re;
}
main()
{
    scanf("%lld%lld%lld", &n, &m, &need);
    for (int i = 1, srx, sry; i <= m; i++)
    {
        scanf("%lld%lld%lld%lld", &srx, &sry, &b[i].cost, &b[i].ki);
        ++srx, ++sry;
        b[i].from = srx, b[i].to = sry;
        if (!b[i].ki)
            ++nw;
    }
    printf("%lld\n", ef());
    return 0;
}

By 沙茶 Cansult