WQS 二分

[国家集训队] Tree I

题目描述

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

题目保证有解。

输入格式

第一行 \(V,E,need\) 分别表示点数，边数和需要的白色边数。

接下来 \(E\) 行，每行 \(s,t,c,col\) 表示这边的端点（点从 \(0\) 开始标号），边权，颜色（\(0\) 白色 \(1\) 黑色）。

输出格式

一行，表示所求生成树的边权和。

样例 #1

样例输入 #1

1
2
3
2 2 1
0 1 1 1
0 1 2 0

样例输出 #1

1
2

提示

对于 \(5\%\) 的数据，\(V\leq 10\)。

对于另 \(15\%\) 的数据，\(V\leq 15\)。

对于 \(100\%\) 的数据，\(V\leq 5\times10^4,E\leq 10^5\)。

所有数据边权为 \([1,100]\) 中的正整数。

By WJMZBMR

二分给白色边权加上一个权值，如果白色边加的比较多，就把这个权值变大，不然就把这个权值变小，从而实现了无限制进行求解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 10 , maxm = 1e5 + 10;
int fa[maxn];
struct node{
	int u,v,w,col;
	bool operator <(const node &x)const{
		if(w!=x.w)return w<x.w;
		return col<x.col;
	}
}a[maxm];
int n,m,k;
//并查集找最小生成树
int find(int x){
	while(x!=fa[x])x=fa[x]=fa[fa[x]];
	return x;
}
#define mp make_pair
pair<int,int> check(int x)
{
	for(int i=1;i<=n;i++)fa[i]=i;
    //初始化
    //先全部白色边都加上
	for(int i=1;i<=m;i++)if(a[i].col==0)a[i].w+=x;
	//排序
    sort(a+1,a+1+m);
	int cnt=0,sz=0,sum=0;
    //还能加一些黑色边
	for(int i=1;i<=m;i++)
    {
		int u=a[i].u,v=a[i].v;
		u=find(u),v=find(v);
		if(u!=v)
        {
			fa[u]=v;cnt++;sz+=(!a[i].col);
			sum+=a[i].w;
		}
	}
    //
	for(int i=1;i<=m;i++)
    if(a[i].col==0)a[i].w-=x;
	return mp(sz,sum-x*k);
}
int main(){
	cin>>n>>m>>k;
    //存边
	for(int i=1;i<=m;i++)
    {
		int u,v,w,col;
        cin>>u>>v>>w>>col;
		u++;v++;
		a[i]=(node){u,v,w,col};
	}
    //进行二分斜率
	int L=-100,R=100,ans=0;
	while(L<=R){
		int mid=(L+R)>>1;
		int x=check(mid).first;
		if(x>=k)L=mid+1,ans=mid;
		else if(x<k)R=mid-1;
	}
	cout<<check(ans).second;
	return 0;
}

最小度限制生成树

题目描述

给你一个有 \(n\) 个节点，\(m\) 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足编号为 \(s\) 的节点正好连了 \(k\) 条边。

输入格式

第一行四个数：\(n,m,s,k\)

下面的 \(m\) 行，每行三个整数：\(u,v,w\)，表示有一条 \(u\) 连向 \(v\) 权值为 \(w\) 的边。

输出格式

输出一个数：满足要求的生成树的总边权。

可能会出现无解的情况，如果无解，则输出 Impossible。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
5 7 1 1
1 3 1
2 1 5
4 2 3
2 5 4
5 1 2
3 5 7
4 1 6

样例输出 #1

1
15

提示

数据范围

对于 \(20\%\) 的数据，\(n \le 10\)，\(m \le 30\)。
对于 \(50\%\) 的数据，\(n \le 1000\)，\(m \le 5000\)。
对于 \(100\%\) 的数据，\(1\leq n \le 5\times 10^4\)，$1m ^5 $，\(1\leq k \le 100\)，\(0\leq w\leq 3\times 10^4\)。

注意

本题设有 hack 数据（Subtask \(2\)），计 \(0\) 分，但若没有通过 hack 数据则不算通过本题。

本题也是如此，只是对象换成了与s相连的边而言。细节比上一题多了不少，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 10 , maxm = 5e5 + 10;
const int INF = 0x3f3f3f3f;
struct node{
	int u,v,w;
	bool operator <(const node &x)const
    {
		return w<x.w;
	}
}q1[maxm],q2[maxm];
int n,m,s,k;
int cnt1,cnt2,fa[maxn];
inline int find(int x)
{
	while(x!=fa[x])x=fa[x]=fa[fa[x]];
	return x;
}
#define mp make_pair
pair<int,int> check(int x)
{
	int L1=1,L2=1;
	int cnt=0,sum=0;
	for(int i=1;i<=n;i++)fa[i]=i;
	while(L1<=cnt1 && L2<=cnt2)
    {
		if(q1[L1].w+x<=q2[L2].w)
        {
			node t=q1[L1];
			int u=t.u,v=t.v,w=t.w+x;
			u=find(u);v=find(v);
			if(u!=v)fa[u]=v,cnt++,sum+=w;
			L1++;
		}
		else {
			node t=q2[L2];
			int u=t.u,v=t.v,w=t.w;
			u=find(u);v=find(v);
			if(u!=v)fa[u]=v,sum+=w;
			L2++;
		}
	}
	while(L1<=cnt1)
    {
		node t=q1[L1];
		int u=t.u,v=t.v,w=t.w+x;
		u=find(u);v=find(v);
		if(u!=v)fa[u]=v,cnt++,sum+=w;
		L1++;
	}
	while(L2<=cnt2)
    {
		node t=q2[L2];
		int u=t.u,v=t.v,w=t.w;
		u=find(u);v=find(v);
		if(u!=v)fa[u]=v,sum+=w;
		L2++;
	}
	return mp(cnt,sum-k*x);
}
int main(){
	cin>>n>>m>>s>>k;
	for(int i=1;i<=m;i++){
		int u,v,w;
        cin>>u>>v>>w;
		node t=(node){u,v,w};
		if(u==s || v==s)
        q1[++cnt1]=t;
		else 
        q2[++cnt2]=t;
	}
	sort(q1+1,q1+1+cnt1);
    sort(q2+1,q2+1+cnt2);
	int L=-INF,R=INF;
	if(check(L).first<k || check(R).first>k){puts("Impossible");return 0;}
	int ans=0;
	while(L<=R){
		int mid=(L+R)>>1;
		if(check(mid).first>=k)ans=mid,L=mid+1;
		else R=mid-1;
	}
	cout<<check(ans).second;
	return 0;
}

April Fools' Problem (hard)

题面翻译

\(n\) 道题, 第 \(i\) 天可以花费 \(a_i\) 准备一道题, 花费 \(b_i\) 打印一道题, 每天最多准备一道, 最多打印一道, 准备的题可以留到以后打印, 求最少花费使得准备并打印 \(k\) 道题。

题目描述

The plans for HC $ ^{2} $ are rather far-fetched: we are just over 500 000 days away from HC $ ^{2} $ 3387, for example, and accordingly we are planning to have a couple hundred thousand problems in that edition (we hope that programming contests will become wildly more popular). The marmots need to get to work, and they could use a good plan...

输入格式

Same as the medium version, but the limits have changed: $ 1<=k<=n<=500000 $ .

输出格式

Same as the medium version.

样例 #1

样例输入 #1

1
2
3
8 4
3 8 7 9 9 4 6 8
2 5 9 4 3 8 9 1

样例输出 #1

1
32

其实不是一上来就学这个，而是要学反悔贪心的。

这题其实很好反悔，如果遇到比较小的时间来打印就打印，然后放一个-b[i]进去，用来抵消.

加的那个权值就是给打印加的了（因为k是限制的是打印）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int maxn = 5e5 + 10;
LL a[maxn],b[maxn];
int n,k;
#define read() read<LL>()
#define Pair pair<LL,int>
#define mp make_pair
priority_queue<Pair,vector<Pair>,greater<Pair> > q;
pair<int,LL> check(LL x)
{
	while(q.size())q.pop();
	int cnt=0;LL sum=0;
	for(int i=1;i<=n;i++)
    {
		q.push(mp(a[i],0));
		LL tmp=b[i]-x+q.top().first;
		if(tmp<0)
        {
			sum+=tmp;
            q.pop();
			q.push(mp(-b[i]+x,1));
		}
	}
	while(q.size())
    cnt+=q.top().second,q.pop();
	return mp(cnt,sum+1LL*k*x);
}
int main(){
	cin>>n>>k;
	for(int i=1;i<=n;i++)
    cin>>a[i];
	for(int i=1;i<=n;i++)
    cin>>b[i];
	LL L=0,R=2e9;
	int ans=0;
	while(L<=R)
    {
		LL mid=(L+R)>>1;
		if(check(mid).first>=k)ans=mid,R=mid-1;
		else L=mid+1;
	}
	cout<<check(ans).second;
	return 0;
}

参考资料：

[总结] wqs 二分 - ¶凉笙 - 博客园 (cnblogs.com)

洛谷日报-wqs二分 学习笔记