wqs二分。。。真乃神人也

给你一个无向带权连通图，每条边是黑色或白色。让你求一棵最小权的恰好有

d

条白色边的生成树。

已知（玄学，蒙吧）：设

d == i

时答案为

g(i)

，则所有

(i,g(i))

构成的图像为一个凸包。

然后二分切线斜率

k

。

此时的

b

是把所有白边的权

-=k

之后跑一遍Kruskal模板得到的结果。

同时，i就是Kruskal最小生成树中白边的数量。

由此，可以得到

g(i) = ki +b

，即求出了

(i,g(i))

的结果。

然后，如果

i == d

，直接结束；

否则根据

i

与

d

的关系改变斜率（

d

在

i

左边就减小斜率，

d

在

i

右边就增大斜率）。

然后就可以最后求出

(d,g(d))

啦！时间复杂度

O(emm我不知道)

我的代码：

CPP

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5;
#define int long long
int V,E,d;
struct edge{
	int u,v,w;
	bool col;
}e[N];
int k,b;
bool cmp(edge A,edge B)
{
	if (A.w - k * (!A.col) == B.w - k * (!B.col)) return A.col < B.col;//这里！！！添加了边权相等优先选白边的政策
	return A.w - k * (!A.col) < B.w - k * (!B.col);
}
int g(int x)
{
	return k * x + b;
}
//并查集↓ 
int fa[N];
void init(){
	for (int i = 0;i <= V;i++)
	{
		fa[i] = i;
	}
}
int gets(int x)
{
	if (fa[x] == x) return x;
	return fa[x] = gets(fa[x]);
}
void merge(int x,int y)
{
	int fx = gets(x),fy = gets(y);
	if (fx != fy) fa[fy] = fx;
}
//并查集↑ 
struct xOy{
	int x,y;
};
xOy Kruskal(int mid)
{
	int cnt = 0,sum = 0,whitecnt = 0;
	sort(e+1,e+E+1,cmp);
	init();
	for (int i = 1;i <= E;i++)
	{
		if (cnt == V-1) break;
		int u = e[i].u,v = e[i].v,w = e[i].w,col = e[i].col;
		if (gets(u) != gets(v))
		{
			merge(u,v);
			cnt++;
			sum += w - k*(!col);
			if (!col) whitecnt++;
		}
	}
	return (xOy){whitecnt,sum};
}
signed main()//王钦石二分 直接拿下 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>V>>E>>d;
	int s,t,c;
	bool col;
	for (int i = 1;i <= E;i++)
	{
		cin>>s>>t>>c>>col;
		e[i] = {s,t,c,col};
	}
	int l = -105,r = 105,mid,i,b,ans;
	while (l <= r)
	{
		mid = (l + r) / 2;
		k = mid;//将斜率k设为mid
		xOy chk = Kruskal(mid);
		i = chk.x;
		b = chk.y;
		if (d <= i)
		{
			ans = b + k*d;//统计答案时手动加上kd
			r = mid - 1;
		}
		else
		{
			l = mid + 1;
		}
	}
	cout<<ans;
	return 0;
}

wqs二分。。。真乃神人也

文章操作

相关推荐

评论

wqs二分。。。真乃神人也