题解 P4806【[CCC2017] 最小费用流】

· · 题解

给定一张 n 个点，m 条边的带权无向图，其中前 n-1 条边为黑色并构成一棵树，其它边为白色。你需要给出一棵生成树，使得将其中一条边 (u,v,w) 的边权减去 \min(w,d) 后，边权总和最小的同时黑边数量最多。

首先需要构造出边权和最小的生成树。不难想到最小生成树。在构造出最小生成树后，把最大的边权减去 d 即可。这样显然是最优的。

然后考虑黑边数量最多的条件。首先这棵最小生成树的黑边要最多。这个很简单，排序时将边权设为第一关键字，边的颜色设为第二关键字就行了。

但这棵生成树的黑边个数就是最终答案了吗？

当然不一定。你可以用一条不在生成树的黑边换掉在生成树的白边，并使得最后的边权和相同。这可以拆解为三个条件：

倍增可以轻松解决问题。时间复杂度 O(m\log m+(n+m)\log n)。

#include<bits/stdc++.h>
#define ll long long 
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rof(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
const int Maxn=2e5;

inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}

struct Node{int u,v,w,typ;} Edge[Maxn+5];
inline bool operator<(Node a,Node b) {return (a.w!=b.w?a.w<b.w:a.typ<b.typ);}
inline bool operator>(Node a,Node b) {return (a.w!=b.w?a.w>b.w:a.typ>b.typ);}
int n,m,d,cnt,sum,ans,fa[Maxn+5],vis[Maxn+5];
inline int Find(int x) {return fa[x]==x?x:fa[x]=Find(fa[x]);}

struct Graph
{
    struct Point{int to,nxt,w;} E[Maxn*2+5];
    int Head[Maxn+5],tot;
    inline void Addedge(int x,int y,int z)
    {
        E[++tot]=(Point){y,Head[x],z};
        Head[x]=tot;
    }
    int val[Maxn+5],fa[Maxn+5],anc[Maxn+5][20];
    int num[Maxn+5][20],dep[Maxn+5];
    inline int fmin(int x,int y) {return Edge[x]>Edge[y]?x:y;}
    inline void dfs(int x,int f)
    {
        fa[x]=anc[x][0]=f,num[x][0]=val[x],dep[x]=dep[f]+1;
        For(i,1,19) anc[x][i]=anc[anc[x][i-1]][i-1],
                    num[x][i]=fmin(num[x][i-1],num[anc[x][i-1]][i-1]);
        for(int i=Head[x];i;i=E[i].nxt)
        {
            int y=E[i].to;
            if(y==f) continue;
            val[y]=E[i].w,dfs(y,x);
        }
    }
    inline int LCA(int x,int y)
    {
        int res=0;
        if(dep[x]<dep[y]) swap(x,y);
        Rof(i,19,0) if(dep[anc[x][i]]>=dep[y])
            res=fmin(res,num[x][i]),x=anc[x][i];
        if(x==y) return res;
        Rof(i,19,0) if(anc[x][i]!=anc[y][i])
            res=fmin(res,num[x][i]),res=fmin(res,num[y][i]),
            x=anc[x][i],y=anc[y][i];
        return fmin(res,fmin(num[x][0],num[y][0]));
    }
    inline void Build() {dfs(1,0);}
} G;

int main()
{
    n=read(),m=read(),d=read();
    For(i,1,m)
    {
        int a=read(),b=read(),c=read();
        if(i<n) Edge[i]=(Node){a,b,c,0};
        else Edge[i]=(Node){a,b,c,1};
    }
    For(i,1,n) fa[i]=i;
    sort(Edge+1,Edge+m+1);
    For(i,1,m)
    {
        int u=Edge[i].u,v=Edge[i].v;
        if(Find(u)!=Find(v))
        {
            fa[Find(u)]=Find(v),vis[i]=1;
            if(!Edge[i].typ) cnt++;
            G.Addedge(u,v,i),G.Addedge(v,u,i);
            sum=max(sum,min(d,Edge[i].w));
        }
    }
    ans=cnt,G.Build();
    For(i,1,m)
    {
        if(vis[i] || Edge[i].typ==1) continue;
        int u=Edge[i].u,v=Edge[i].v,w=Edge[i].w;
        int id=G.LCA(u,v);
        if(Edge[id].typ==0) continue;
        if(sum==Edge[id].w+min(d,Edge[i].w)-Edge[i].w)
            ans=cnt+1;
    }
    printf("%d\n",n-1-ans);
    return 0;
}