LinhoNotes

外观

假期练习 #3 ​

Stop learning useless algorithms, go and solve some problems, learn how to use binary search

T3.1 P2619 [国家集训队] Tree I ​

解题思路 ​

首先，这不是明摆着要求最小生成树吗？

那么，在某一次的求 MST 时，我们可以统计白边的数量

其只有可能呈现三种情况：

  1. 刚好为 need
  2. 比 need 大
  3. 比 need 小

当白边数量刚好为 need 的时候，就是一个合法的答案

当出现另外两种情况时，我们有没有什么方法来调整答案中白边的数量呢？

有的，兄弟，有的，这样的办法我们有一种：

众所周知，在跑 kruskal 的时候，我们有这样一句代码：

c++
sort(e + 1, e + 1 + m, cmp);

这是对边进行排序，由此可知，边权越小越靠前

那我们可以将白边统一放大 / 缩小，来改变边的顺序，进而改变我们决策时白边的数量

但是这样我们就改变了边的权值，对于我们计算答案有没有影响呢？

考虑到对于最终的解，白边的数量是固定为 need 的

所以我们将白边统一加上 add ，最后的合法的答案相当于都加上了 add∗need

显然，这样是不会影响正确性的

那解法就呼之欲出了：

  • 二分调整 add
  • 每次 check 的时候求最小生成树统计白边数量

代码中需要一些细节和特判，由于煮波深受其害，就不在这里放出了（坏笑）

AC 代码 ​

c++
#include <bits/extc++.h>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rnd(time(0));
typedef long long ll;
typedef uint64_t ull;
template <typename T> using vct = vector<T>;
template <typename T> using v2ct = vector<vector<T>>;
template <typename T> using v3ct = vector<vector<vector<T>>>;

template <typename T, typename Compare = std::less<T>>
using oset = tree<T, null_type, Compare, rb_tree_tag,
                  tree_order_statistics_node_update>;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt = 1;

struct Edge {
    ll u, v, w, col;
    bool operator<(const Edge &_t) {
        if (w != _t.w)
            return w < _t.w;
        return col < _t.col;
    }
};

ll get_fa(vector<ll> &fa, ll x) {
    if (fa[x] == x)
        return x;
    return fa[x] = get_fa(fa, fa[x]);
}

void joint(vector<ll> &fa, ll x, ll y) {
    ll fax = get_fa(fa, x), fay = get_fa(fa, y);
    if (fax == fay)
        return;
    fa[fax] = fay;
}

void solve() {
    ll n, m, need, ans = 0;
    cin >> n >> m >> need;
    vector<Edge> eg(m + 1);
    for (ll i = 1; i <= m; i++) {
        cin >> eg[i].u >> eg[i].v >> eg[i].w >> eg[i].col;
    }
    //	sort(eg.begin()+1,eg.end());

    auto check = [&](ll x) -> ll {
        //		cout<<"!!!"<<endl;
        vector<ll> fa(n + 1);
        for (ll i = 1; i <= n; i++)
            fa[i] = i;
        for (ll i = 1; i <= m; i++)
            if (eg[i].col == 0)
                eg[i].w += x;

        sort(eg.begin() + 1, eg.end());
        ll cnt = 0, cur = 0, flag = 0, res = 0;
        while (cnt < n - 1) {
            Edge e = eg[++cur];
            if (get_fa(fa, e.u) == get_fa(fa, e.v))
                continue;
            joint(fa, e.u, e.v);
            res += e.w;
            flag += (e.col + 1) % 2;
            cnt++;
        }
        for (ll i = 1; i <= m; i++)
            if (eg[i].col == 0)
                eg[i].w -= x;
        if (flag >= need)
            ans = res - need * x;
        if (flag >= need)
            return 1;
        else
            return 0;
    };

    ll l = -100, r = 100;
    while (l < r) {

        ll mid = (l + r + 1) / 2;
        ll flag = check(mid);

        //		cout<<"!!!"<<endl;

        if (flag)
            l = mid;
        else
            r = mid - 1;
    }

    //	OOO
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //	cin >> tt;	//非多组测试数据时注释掉即可

    while (tt--) {
        solve();
    }

    cout.flush();
    return 0;
}

T3.2 P5633 最小度限制生成树 ​

解题思路 ​

有了上一题的铺垫，解法显而易见

AC 代码（基本没改） ​

c++
#include <bits/extc++.h>
#define OOO cout << ">>>>"; // 调试标识

using namespace std;
using namespace __gnu_pbds;

mt19937_64 rnd(time(0));
typedef long long ll;
typedef uint64_t ull;
template <typename T> using vct = vector<T>;
template <typename T> using v2ct = vector<vector<T>>;
template <typename T> using v3ct = vector<vector<vector<T>>>;

template <typename T, typename Compare = std::less<T>>
using oset = tree<T, null_type, Compare, rb_tree_tag,
                  tree_order_statistics_node_update>;

const ll INF = 1e18, Mod = 1e9 + 7;

ll tt = 1;

struct Edge {
    ll u, v, w, col;
    bool operator<(const Edge &_t) {
        if (w != _t.w)
            return w < _t.w;
        return col < _t.col;
    }
};

ll get_fa(vector<ll> &fa, ll x) {
    if (fa[x] == x)
        return x;
    return fa[x] = get_fa(fa, fa[x]);
}

void joint(vector<ll> &fa, ll x, ll y) {
    ll fax = get_fa(fa, x), fay = get_fa(fa, y);
    if (fax == fay)
        return;
    fa[fax] = fay;
}

void solve() {
    ll n, m, s, need, ans = 0, scnt = 0;
    cin >> n >> m >> s >> need;

    vector<Edge> eg(m + 1);
    for (ll i = 1; i <= m; i++) {
        cin >> eg[i].u >> eg[i].v >> eg[i].w;
        if (eg[i].u == s || eg[i].v == s)
            eg[i].col = 0, scnt++;
        else
            eg[i].col = 1;
    }

    //	sort(eg.begin()+1,eg.end());

    auto check = [&](ll x) -> ll {
        //		cout<<"!!!"<<endl;
        vector<ll> fa(n + 1);
        for (ll i = 1; i <= n; i++)
            fa[i] = i;
        for (ll i = 1; i <= m; i++)
            if (eg[i].col == 0)
                eg[i].w += x;

        sort(eg.begin() + 1, eg.end());
        ll cnt = 0, cur = 0, flag = 0, res = 0;
        while (cnt < n - 1) {
            Edge e = eg[++cur];
            if (get_fa(fa, e.u) == get_fa(fa, e.v))
                continue;
            joint(fa, e.u, e.v);
            res += e.w;
            flag += (e.col + 1) % 2;
            cnt++;
        }
        for (ll i = 1; i <= m; i++)
            if (eg[i].col == 0)
                eg[i].w -= x;
        if (flag >= need)
            ans = res - need * x;
        return flag;
    };

    if (check(1000000) > need || check(-1000000) < need) {
        cout << "Impossible" << endl;
        return;
    }

    ll l = -30000, r = 30000;
    while (l < r) {

        ll mid = (l + r + 1) / 2;
        ll flag = check(mid);

        //		cout<<"!!!"<<endl;

        if (flag >= need)
            l = mid;
        else
            r = mid - 1;
    }

    //	OOO
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    //	cin >> tt;	//非多组测试数据时注释掉即可

    while (tt--) {
        solve();
    }

    cout.flush();
    return 0;
}