题解 P2619 【[国家集训队2]Tree I】

· · 题解

这个题吧，说难也不难，说简单也不简单

其实题目给的很明确
让你求一棵最小权的恰好有need条白色边的生成树。
这不是明摆着要求最小生成树吗？
刚要开始写，问题接踵而至，这个白边的数量怎么控制呢，如果多了或者少了，如何增减？

进入正题： 总所周知，在跑kruskal的时候，我们有这样一句代码：

sort(e+1,e+1+m,cmp);

这是对边进行排序，由此可知，边权越小越靠前
我们可以通过改变白边的权值来改变它出现的位置

例如need=3，但是此时我的最小生成树上有4条白边，那么我可以全部加上一个数，然后某条白边突然比最小的黑边大了，我再跑kruskal，更新之后的最小生成树就会把一条大的白边扔到后边去，替换成一条黑边，那么此时白边条数就少了1，满足答案，统计答案时把加的这个数减掉就行了

现在我们来说说怎么确定要加的这个数
我们采取二分答案的办法，因为题目中说道边权在[1,100]所以定义l=-111,r=111,然后二分往白边上加权值，最后一定能卡出来一个合适的解

那么问题又来了，如果说当前白边加上mid后，白边条数temp>need了，然鹅，如果加上mid+1后，temp<need了，这可咋整，难搞哟~~

题目中说到了：保证有解，所以出现上述情况时一定有黑边==白边的边权
so，我们只需要把一条黑边换成白边就好啦
在白边条数temp>need时更新答案
最终答案 ans=sum-mid×need

代码时间：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int fa[1000010];
int n,m,need;
struct node{
    int s,t,v,c;//起点、终点、权值、颜色
}e[1000010];

inline bool cmp(node a,node b){//排序
    if(a.v==b.v) return a.c<b.c;
    else return a.v<b.v;
}

inline int find(int x){//并查集不会赶紧学去
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}

int sum,ans,temp;
int cnt=0;
inline void kruskal(){//板子
    sort(e+1,e+1+m,cmp);
    for(int i=1;cnt!=n-1;i++){
        int xx=find(e[i].s),yy=find(e[i].t);
        if(xx==yy) continue;
        if(xx!=yy){
            cnt++;
            fa[xx]=yy;
            if(e[i].c==0) temp++;//统计白边数量
            sum+=e[i].v;
        } 
    }
}

int main(){
    cin>>n>>m>>need;
    for(int i=1;i<=m;i++){
        cin>>e[i].s>>e[i].t>>e[i].v>>e[i].c;
        e[i].s++,e[i].t++;//注意！因为题面说0开始标号
    }
    int l=-111,r=111;//二分，初始值比100大就行
    while(l<=r){
        int mid=(l+r)>>1;
        for(int i=1;i<=m;i++)
            if(e[i].c==0)
                e[i].v+=mid;//白边加权
        for(int i=1;i<=n+1;i++)
            fa[i]=i;//初始化
        sum=0,cnt=0,temp=0;//每次要清空
        kruskal();
        if(temp>=need){
            l=mid+1;
            ans=sum-need*mid;//更新答案
        }
        else r=mid-1;
        for(int i=1;i<=m;i++)
            if(e[i].c==0)
                e[i].v-=mid;//最终要把加上的减掉
    }
    cout<<ans<<'\n';//over
    return 0;
}

感觉讲的挺明白了叭，不懂评论区见，溜~~~