洛谷P2619 [国家集训队]Tree I

can can need?一道很好的二分题目,阐释了进阶的二分思想的运用,扩展了原本二分局限的思想. 原本我一直认为二分都是一些满足单调性的东西,虽然这个题也确实是,但是它的单调性其实是比较模糊的。 求最小生成树,但是要求白边的边数一定是 n e e d need need情况下的. 考虑下二分出这个 c o s t cost cost,接下来是检验能否在指定的 c o s t cost cost内,是否能找到 n e e d 条白边 need条白边 need条白边, n − 1 − n e e d n-1-need n−1−need条黑边的生成树. 然后我就又又又没有思路,以上仍然是胡编乱造的,去看题解了. 原来我理解错题目的意思了,意思 首先对原始的边进行Kruskal，随便跑出一个MST,假设有 x x x条白边. 接下来对 x x x讨论,如果 x > n e e d x>need x>need,证明白边的边权是比较小的,我们需要把一些白边替换成黑边,如何替换呢,我们考虑整体把原本白色的边的边权稍加修改,如果 x > = n e e d x>=need x>=need,说明白边比较多,考虑把它扔到后边 把边权整体加上 y 把边权整体加上y 把边权整体加上y.反之,如果 x < n e e d x=need x>=need情况,我们需要更新一次答案.

/*
You held me down but I broke free,
I found the love inside of me.
Now I don't need a hero to survive
Cause I already saved my life.
*/
#include
using namespace std;
const int maxn = 1000010;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
#define all(a) (a).begin(), (a).end()
#define pb(a) push_back(a)
vector G[maxn];
struct Edge{
	int u,v,w,c;
}edge[maxn];
bool cmp(Edge a,Edge b){
	if(a.w==b.w) return a.cm>>need;
	for(int i=1;i>edge[i].u>>edge[i].v>>edge[i].w>>edge[i].c;
		edge[i].u++,edge[i].v++;
	}
	int L = -111,R = 111;ll ans = -1;
	while(L