Tree 洛谷 P2619
一道生成树的很好的题目
题目描述
给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有 need 条白色边的生成树。
乍一看还是很没有头绪的（反正刚开始我没有
思路
由于我们需要求一个最小权的，恰好有 need 条边的生成树
首先可以想到一个贪心的作法就是我先把最小的白边加入生成树之中直到 need 条跑 MST
再把黑边跑 MST 加入生成树中
但显然。。。这个贪心的策略非常不对。。。
因为白边的长度和加上黑边的长度和才会是总长度和，如果黑边要加入 2 条边，共有三条边，为 1,2,99999……黑边是会影响到白边的选取的，所以我们需要从整体上考虑问题，考虑同时加入白边黑边的时候应该如何进行选取最优
那我们先跑一遍 MST，求出加入的白边的个数此时加入的百变个数与 need 一定是有差别的（如果等于了直接输出就可以了）
我们想要从整体上考虑问题，那么我们就改变 MST 的过程就好了
但是怎么改变就是一个问题……
kruskar 的过程是要进行排序的，那我们就……改变权值就可以了呀！
我们将白边的权值进行改变，在每次与 need 不相符的时候就进行一次改变权值，就可以进行对百变加入生成树的过程的改变
如果我们将白边的权值增大以至于最小的可以加入的次小黑边，就将那条黑边加入，把这条黑边弹出，这样我们是可以获得最小的取出一条白边的代价的（因为需要一点点增加）
所以正解思路就具备了
实现
实现过程中，我们将白边的权值一点点的改变……
聪明的同学就想到了：
复杂度可能有点不对（然后开始 diss 我）
不要着急。。。题目中给定的边权是小于等于 100 的，我们进行二分就可以了呀
二分答案是一个很好的东西（虽然在这道题中不二分似乎也可以过去，我没有试验过，但是数据范围改一改就可以看到二分答案的优势了）
代码
（由于是过了好长时间才回来写的博客所以有点生疏了）
#include<bits/stdc++.h>
using namespace std;
#define maxn 100010
#define int long long
int v,e,need;
struct node{
int u,v,val,c;
}a[maxn];
bool cmp(node a1,node a2)
{
if(a1.val==a2.val)return a1.c<a2.c;//排序
return a1.val<a2.val;
}
int fa[maxn];
int find(int x)
{
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y)
{
x=find(x);y=find(y);
fa[x]=y;
}
int ans,check;
void kruskal()
{
ans=0;check=0;
for(int i=1;i<=v+1;i++)fa[i]=i;
int cnt=0;
sort(a+1,a+1+e,cmp);
for(int i=1;cnt!=v-1;i++)
{
int aa=find(a[i].u),bb=find(a[i].v);
if(aa!=bb)
{
if(a[i].c==0)check++;//白边
merge(aa,bb);
ans+=a[i].val;
cnt++;
}
}
//kruskal判断这一次进行MST后生成树的白边数量
}
int num;
signed main()
{
cin>>v>>e>>need;
for(int i=1;i<=e;i++)
{
cin>>a[i].u>>a[i].v>>a[i].val>>a[i].c;
a[i].u++;a[i].v++;
}
int l=-105,r=105;
while(l<=r)
{
int mid=(l+r)>>1;
for(int i=1;i<=e;i++)
if(!a[i].c)a[i].val+=mid;
kruskal();
if(check>=need){
l=mid+1;
num=ans-need*mid;
}
else r=mid-1;
for(int i=1;i<=e;i++)
if(!a[i].c)a[i].val-=mid;
//对要加的长度进行二分答案，最后的结果再减去白边所加上的权值和
}
cout<<num<<endl;
return 0;
}