P2619 题解+带权二分记录

__vector__ · 2022-08-03 19:11:50 · 个人记录

做法

首先忽略 need 条白边的限制。
设 f(x) 表示有 i 条白边时的最小边权和。

由题解可知，这个函数是个凸函数。

对于这个函数，难以直接求出其中某个点的值，但是可以轻松求出它的最小值点。

所以，可以试着让 need 点成为值最小的点。

现在已知值最小的点 m，尝试让它向 need 点靠近。

如果 m 点在 need 点左边，那么将所有白边的权值加上 w(w \ge 0)，使得 m 点向右移动（因为白边权值增加了，求最小生成树时，使用的白边数量减少，从而使得最小值点向左移动）。

反之亦然。

现在要做的，就是二分 w，使得 need 点与 m 点重合（need 点成为值最小的点）

二分出 w 之后，还要把求得的最小边权和减去 w \cdot need，消去影响。

Code

/*
Sto pt orz
Sto zgc orz
Sto lhx orz
Sto tyy orz
*/
#include <bits/stdc++.h>
using namespace std;
namespace Main
{
    typedef pair<int,int> PII;
    const int maxv=5e4+5;
    const int maxe=1e5+5;
    struct EDGE
    {
        int u,to,c,col;
        bool operator <(const EDGE& b)
        {
            return (c!=b.c)?(c < b.c):(col<b.col);
        }
    }edge[maxe];
    int cnt;
    inline void add(int s,int t,int c,int col)
    {
        edge[++cnt].to=t;
        edge[cnt].u=s;
        edge[cnt].c=c;
        edge[cnt].col=col;
    }
    int fa[maxv];
    int find(int x)
    {
        return x==fa[x]?x:fa[x]=find(fa[x]);
    }
    int V,E,need;
    PII kruskal()
    {
        sort(edge+1,edge+E+1);
        int ans=0;
        int ecnt,whicnt;
        ecnt=whicnt=0;
        for(int i=1;i<=E;i++)
        {
            int a=edge[i].u,b=edge[i].to;
            if(find(a)!=find(b))
            {
                fa[find(a)]=find(b);
                ans+=edge[i].c;
                ecnt++;
                if(edge[i].col==0)whicnt++;
            }
            if(ecnt==V-1)break;
        }
        return make_pair(ans,whicnt);
    }
    void main()
    {
        scanf("%d%d%d",&V,&E,&need);
        int si,ti,ci,coli;
        for(int i=1;i<=E;i++)
        {
            scanf("%d%d%d%d",&si,&ti,&ci,&coli);
            add(si+1,ti+1,ci,coli);
        }
        int l=-111,r=111;
        int ans=0;
        while(l<=r)
        {
            int mid=l+r>>1;
            for(int i=1;i<=V;i++)fa[i]=i;
            for(int i=1;i<=E;i++)
            {
                if(edge[i].col==0)edge[i].c+=mid;
            }
            PII sto_pt_orz=kruskal();
            if(sto_pt_orz.second>=need)
            {
                ans=sto_pt_orz.first-need*mid;
                l=mid+1;
            }
            else
            {
                r=mid-1;
            }
            for(int i=1;i<=E;i++)
            {
                if(edge[i].col==0)edge[i].c-=mid;
            }
        }
        printf("%d",ans);
    }
}
int main()
{
    Main::main();
    return 0;
}