P4806 [CCC2017] 最小费用流 题解

Exp10re · 2024-05-01 10:59:39 · 题解

你怎么知道我在赛时 20 分钟过了这道题。

题解

看题面，注意到当 D=0 时就是最小生成树。

在满足最小生成树的条件下，我们还希望原始树边尽可能多。因此我们在运行 Kruskal 算法之前的排序时将权值作为第一关键字，是否为原始树边作为第二关键字进行排序，根据贪心思想显然在得到最小生成树时原始树边最多。

现在考虑 D \ne 0 的情况：先跑一边上述最小生成树。

注意到 val \leftarrow \min(0,val-D) 只能作用于一条树边，因此前 n-2 小的边都与 D 无关。

记权值最大的边权值为 V，显然无法选取排序后编号严格小于这条边的边，由此可得无法选取权值小于 V 的边，则有以下分类讨论：

• 若 V \gt D，则有：
  • 选取其他权值为 V 的边一定不比选择该边更优。
  • 选取权值大于 V 的边会影响最小生成树的权值之和。
• 若 V \leq D，则有：
  • 选取权值在 [V,D] 范围内的边不会影响最小生成树的权值之和。
  • 考虑将这一范围内的边按照是否为原始树边作为第一关键字进行排序剩余边不变，再选取最后一条边。
  • 答案变化量显然为 1。

然后就没了。

代码

#include<bits/stdc++.h>
using namespace std;
const long long MAXN=202002;
struct edg
{
    long long val,u,v,isd;
};
bool cmp(edg ta,edg tb)
{
    return ta.val==tb.val?ta.isd>tb.isd:ta.val<tb.val;
}
bool cmp2(edg ta,edg tb)
{
    return ta.isd>tb.isd;
}
edg edge[MAXN];
long long fa[MAXN],n,m,d;
long long find(long long x)
{
    while(x!=fa[x])
    {
        fa[x]=fa[fa[x]];
        x=fa[x];
    }
    return x;
}
void merge(long long ta,long long tb)
{
    ta=find(ta);
    tb=find(tb);
    fa[ta]=tb;
    return;
}
int main()
{
    scanf("%lld%lld%lld",&n,&m,&d);
    long long i,j,ta,tb,tc,cnt=0,ans=0,rec;
    for(i=1;i<=n;i++)
    {
        fa[i]=i;
    }
    for(i=1;i<=n-1;i++)
    {
        scanf("%lld%lld%lld",&ta,&tb,&tc);
        edge[i].u=ta;
        edge[i].v=tb;
        edge[i].val=tc;
        edge[i].isd=1;
    }
    for(i=n;i<=m;i++)
    {
        scanf("%lld%lld%lld",&ta,&tb,&tc);
        edge[i].u=ta;
        edge[i].v=tb;
        edge[i].val=tc;
        edge[i].isd=0;
    }
    sort(edge+1,edge+1+m,cmp);
    for(i=1;i<=m;i++)
    {
        if(find(edge[i].u)!=find(edge[i].v))
        {
            merge(edge[i].u,edge[i].v);
            cnt++;
            ans+=edge[i].isd^1;
        }
        if(edge[i].val<=d)
        {
            if(cnt==n-2)
            {
                break;
            }
        }
        else
        {
            if(cnt==n-1)
            {
                break;
            }
        }
    }
    if(cnt==n-2)
    {
        rec=i+1;
        for(i=rec;i<=m;i++)
        {
            if(edge[i].val>d)
            {
                break;
            }
        }
        sort(edge+rec,edge+i,cmp2);
        for(i=rec;i<=m;i++)
        {
            if(find(edge[i].u)!=find(edge[i].v))
            {
                merge(edge[i].u,edge[i].v);
                cnt++;
                ans+=edge[i].isd^1;
            }
            if(cnt==n-1)
            {
                break;
            }
        }
    }
    printf("%lld",ans);
    return 0;
}