代码写的可能比较繁琐,请见谅。

思路

首先考虑 \(\text{wqs}\) 二分。

对所有连向 \(s\) 的边进行定量偏移。

即所有连向 \(s\) 的边的边权 \(q\) 加上二分的定量 \(\Delta\)

就可以将这一个问题变成一个可行性问题。

可能比较困难的一点就是当 \(\Delta\) 一定时,可能拥有不同的 \(k\) 的方案。

本篇主要讲述如何构造一个正确的方案。

首先判断一个无解的情况。

  1. \(s\) 的出边不足 \(k\)
  2. 原图不联通。
  3. 使原图联通 \(s\) 必须连的出边超过 \(k\)

除去上面三种情况,所有的情况必然会有一个解。

考虑对于一个偏移量如何构造出这样的一个解。

首先可以构造出一组 \(s\) 出边最少的解。

考虑在此基础上将其增加至 \(k\) 条出边。

对于相同权值的边,我们先将原方案中所连的出边进行连接。

然后如果不足 \(k\) 条出边,再去考虑相同权值下的其他出边。

最后再去考虑相同权值下的其他边。

可以发现,原方案中所连的出边一定还会在新方案中被连。

这是由于虽然我们增加了一些边,但对于原方案中所连的出边所更改的联通性是不会进行改变的(不然就会出现在原方案中)。

容易发现这样也一定不会比原方案更劣(原理大致与朴素的 \(\text{kruskal}\) 差不多),并且一定有解。

这样就有了一个大致的算法流程。

具体可以看代码。

Code

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1000010;

int n, m, k, s, kl, top, fa[N], vis[N], ans[N];

class Graph
{
public:
    int cnt;
    struct edge
    {
        int to, nxt, val, id;
    } e[N];
    inline edge &operator[](int tmp) { return e[tmp]; }
    inline void init(int x)
    {
        for (int i = 1; i <= cnt; i++)
            e[i].val += x;
    }
    inline void add(int x, int y, int z, int i) { e[++cnt] = {x, y, z, i}; }
    inline void mySort()
    {
        sort(e + 1, e + cnt + 1, [](edge a, edge b)
             { return a.val < b.val; });
    }
} graBlack, graWhite;

inline int read()
{
    int asd = 0, qwe = 1;
    char zxc;
    while (!isdigit(zxc = getchar()))
        if (zxc == '-')
            qwe = -1;
    while (isdigit(zxc))
        asd = asd * 10 + zxc - '0', zxc = getchar();
    return asd * qwe;
}

inline bool check(int x, int y) { return (x == s || y == s); }
inline int gf(int x) { return (fa[x] == x ? fa[x] : fa[x] = gf(fa[x])); }

inline bool merge(int x, int y)
{
    int fx = gf(x), fy = gf(y);
    if (fx == fy)
        return 0;
    fa[fx] = fy;
    return 1;
}

inline int kruskal()
{
    int num = 0;
    top = 0;
    iota(fa + 1, fa + n + 1, 1);
    for (int i = 1, l = 1, r = 1; i <= m; i++)
        if (l <= graBlack.cnt && graBlack[l].val < graWhite[r].val)
            merge(graBlack[l].to, graBlack[l].nxt), l++;
        else
            num += merge(graWhite[r].to, graWhite[r].nxt), r++;
    return num;
}

inline void checkSol()
{
    int cnt = 0, sum = 0;
    for (int i = 1; i <= graBlack.cnt; i++)
        cnt += merge(graBlack[i].to, graBlack[i].nxt);
    for (int i = 1; i <= graWhite.cnt; i++)
        if (merge(graWhite[i].to, graWhite[i].nxt))
            cnt++, sum++;
    if (cnt != n - 1 || sum > k || graWhite.cnt < k)
        puts("Impossible"), exit(0);
}

inline void makeSol(int mid)
{
    graWhite.init(mid), top = 0;
    iota(fa + 1, fa + n + 1, 1);
    int sum = 0, l = 1, r = 1, i, j;
    for (i = 1; i <= m; i++)
        if (l <= graBlack.cnt && graBlack[l].val <= graWhite[r].val)
            merge(graBlack[l].to, graBlack[l].nxt), l++;
        else
        {
            if (merge(graWhite[r].to, graWhite[r].nxt))
                vis[r] = 1, k--;
            r++;
        };
    l--, r--, top = 0;
    iota(fa + 1, fa + n + 1, 1);
    for (i = 1, j = 1; i <= graBlack.cnt; i++)
    {
        while (j <= r && graWhite[j].val <= graBlack[i].val)
        {
            int ls = j, rs = j;
            int x = graWhite[j].val;
            while (rs < r && graWhite[rs + 1].val == x)
                rs++;
            for (int j = ls; j <= rs; j++)
                if (vis[j] && merge(graWhite[j].to, graWhite[j].nxt))
                    sum += graWhite[j].val, ans[++top] = graWhite[j].id;
            for (int j = ls; j <= rs && k; j++)
                if (merge(graWhite[j].to, graWhite[j].nxt))
                    sum += graWhite[j].val, k--, ans[++top] = graWhite[j].id;
            j = rs + 1;
        }
        if (merge(graBlack[i].to, graBlack[i].nxt))
            sum += graBlack[i].val, ans[++top] = graBlack[i].id;
    }
    while (j <= r)
    {
        int ls = j, rs = j;
        int x = graWhite[j].val;
        while (rs < r && graWhite[rs + 1].val == x)
            rs++;
        for (int j = ls; j <= rs; j++)
            if (vis[j] && merge(graWhite[j].to, graWhite[j].nxt))
                sum += graWhite[j].val, ans[++top] = graWhite[j].id;
        for (int j = ls; j <= rs && k; j++)
            if (merge(graWhite[j].to, graWhite[j].nxt))
                sum += graWhite[j].val, k--, ans[++top] = graWhite[j].id;
        j = rs + 1;
    }
    cout << sum - kl * mid << endl;
}

inline void wqsDichotomous()
{
    int l = -1e9, r = 1e9;
    graBlack.mySort(), graWhite.mySort();
    while (l <= r)
    {
        int mid = (l + r) >> 1;
        graWhite.init(mid);
        int x = kruskal();
        graWhite.init(-mid);
        if (x > k)
            l = mid + 1;
        if (x < k)
            r = mid - 1;
        if (x == k)
            break;
    }
    makeSol((l + r) >> 1);
}

signed main()
{
    n = read(), m = read(), s = read(), kl = k = read();
    iota(fa + 1, fa + n + 1, 1);
    for (int i = 1; i <= m; i++)
    {
        int x = read(), y = read(), z = read();
        if (check(x, y))
            graWhite.add(x, y, z, i);
        else
            graBlack.add(x, y, z, i);
    }
    checkSol(), wqsDichotomous();
    return 0;
}

原文地址:http://www.cnblogs.com/mfeitveer/p/16852549.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性