题解 SP11579 【COMPANYS - Two Famous Companies】

· · 题解

本题第一篇题解QAQ

题目大意：

给出一个图，图中有n个点，m条边，图中每条边非黑即白。

要求：求这张图的最小生成树，且满足刚好有k条白边。

输入：

输入有多个测试数据，对于每个测试数据：

第一行输入三个数：n,m,k

接下来的m行 每行分别四个数：a,b,c,x。

# 输出： 输出 Case i: ans（注意空格） $i$代表这是第$i$组数据 $ans$代表答案（最小权值和） # 数据范围： $1 <= N <= 50000 N-1 <= M <= 100000 0 <= a, b <= N-1, a != b 1 <= c <= 100 x=[0,1]

貌似没给数据组数，但是目测不超过4组

题解：

最开始我以为这是一道裸的最小生成树，然后我写一半发现不对...

正确做法：二分答案 + 最小生成树

不了解最小生成树的最好先去了解一下

进入正题：

我最开始是这么想的：

不是要满足白边条数吗？我先把白边给连到目标个数k，之后再连黑边。

我用的kruskal算法，我想sort之后一定满足连的白边最短，黑边最短，加起来肯定就是最优解。

然后我被狠狠地打脸了

为什么这样不行？我们来看看这张图。

如果你和我最开始思路一样，先选白边，那么权值为1,2,4,9,10的边会被先选走，最后选黑边就不得不选99。

这样选无疑没有白边选1,2,4,10,12，黑边选5 来的小

所以刚刚那个解法是个错解。

正解：

我们不是要求最小生成树吗？

那就求呗。

你说有白边的限制？？我先不去管它就行了。

用kruskal跑过一遍之后，我们确确实实得到了一个最小生成树。只不过，这个最小生成树可能不满足白边要求。

我们用一个计数器，记录我们跑kruskal时选中的白边条数，姑且把它称作wg（"white" + "个数" 的缩写，这中英混杂也是没谁了）

那么我们将会面临两种情况：

对于情况Ⅰ，选少了必然是因为白边权值整体过大引起的，导致一部分黑边排在了前面，抢占了白边的位置。

而对于情况Ⅱ，选多了必然是因为白边权值整体过小引起的，导致一部分过多的白边涌进了数组前方而被选中。

怎么处理这两种情况？

鲁迅说的好：你权值太小我给你拉上来，你权值过大我给你打下去。

如果白边整体权值太小，我们就把所有白边的权值加上一个正值，让整体权值变大。

反之，白边整体权值过大，我们就把所有白边的权值加上一个负值。让整体权值变小。

我们把加上的这个值暂叫做偏移量，用mid表示。（看到mid是不是想起了什么QAQ）

处理完之后再跑一边kruskal，如果仍然不满足，就再重复上述过程。 直到跑了那么一次，终于满足了wg == k，这个时候跑的最小生成树就是我们想要的最小生成树了。

那么我们得到这个最小生成树之后，计算一遍它的总权值。*但是要注意的是：我们每条白边的权值都加上了一个偏移量，所以要对结果减去 （$k mid$）才符合要求。**

有人看到这会问了：

那么今天的压轴嘉宾来了：二分！

当然，有了mid，自然就少不了l,r啦（二分三兄弟）。

显然，mid = (l + r) / 2 ，当如果白边整体权值过小，l = mid + 1，让mid更大，否则r = mid - 1，让mid更小。

当l > r时二分结束。这个时候的mid是被不断调整过的，二分结束之后能够保证mid为正确的偏移量。

为什么我敢说这个mid最终是正确的？只要我让l < -100, r > 100就可以了。又因为l<mid<r，所以最终mid会停留在[-100,100]间

因为任一一条边的权值都不大于100，那么mid必定在[-100,100]范围内，偏移值不可能比所有边的权值还大/小吧。

最极端的两种情况就是白边都为100，黑边都为0，或者 白边都为0，黑边都为100。即便在这种情况，偏移值也不会超出这个范围，最多等于100或者-100罢了。

所以这个mid是跑不脱滴~

这样一来，大部分的东西就处理完了。

最后提一些小细节吧：

大概就是这样了，上代码！！

#include<bits/stdc++.h>
#define mian main
#define QWQ puts("QWQ");

using namespace std;

struct node
{
    int u, v, w, x;//u,v,w,x：连边，被连边，权值，颜色 
}e[100005];

int n, m, k, t;
int ans, sum, wg, g;
//ans:答案，sum:每次跑kruskal记录的最小权值和，wg不解释，g:记录跑kruskal时连了多少边，方便退出
int f[50005];

int _find(int x)//并查集 
{
    while(x != f[x]) x = f[x] = f[f[x]];
    return x;
}

void clean()//清空子函数 
{
    g = wg = sum = 0;
    for(int i = 1; i <= n; i ++)f[i] = i;
}

bool cmp(node a, node b)
{
    if(a.w == b.w)return a.x < b.x;//权值相同，白边优先
    return a.w < b.w;//权值不同，权值小在前 
}

void kruskal()//最小生成树板子 
{
    sort(e + 1, e + 1 + m, cmp);
    for(int i = 1; i <= m; i ++)
    {
        int fu = _find(e[i].u);
        int fv = _find(e[i].v);
        if(fu == fv) continue;//判环 
        f[fu] = fv;
        g ++;//增加总数 
        if(e[i].x == 0) wg ++;//增加白边数 
        sum += e[i].w;//每次计算权值和 
        if(g >= n - 1) break;//达到规定边数退出 
    }
}

int main()
{
    while(~scanf("%d%d%d", &n, &m, &k))//循环读入 
    {
        t ++;//记录数据组数 
        for(int i = 1; i <= m; i ++)
        {
            scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].w, &e[i].x);
            e[i].u ++;
            e[i].v ++;//居然会有编号为0的点，惊了啊QAQ，点的序号要加上1 
        }
        int l = -150, r = 150, mid; 
        while(l <= r)//二分开始 
        {
            mid = (l + r) / 2;//计算中间数，也是加上的偏移量 
            for(int i = 1; i <= m; i ++)
                if(e[i].x == 0) e[i].w += mid;//每个白边权值加上偏移量 
            clean();//每次执行前清除 
            kruskal();//跑最小生成树 
            for(int i = 1; i <= m; i ++)
                if(e[i].x == 0) e[i].w -= mid;//白边权值减回来 
            if(k > wg) r = mid - 1;
            else l = mid + 1, ans = sum - k * mid;
            //计算ans值。因为k条白边都加了一个mid，所以计算时要减回来
            //顺带判断改变l,r值以此改变mid值
        }
        printf("Case %d: %d\n", t, ans);
    }
    return 0;
}

顺带一提，这道题和本题完全一样...就是输入输出略有不同。双倍经验

我也不知道有没有把你们讲懂QAQ，如果没看懂可以去那边看看，希望对你们有帮助。