HDU - 6982 J - Road Discount wqs二分 + 模型转换 + 优化_多校wqs二分

传送门

题意：

给你一个$n$个点$m$条边的图，每个边有一个代价以及折扣价，你需要输出$n$行，第$i$行代表你可以选$i-1$条边使其变成优惠价，问每次的最小生成树的代价是多少。
$n\le 1e3,m\le 2e5,c_i,d_i\le 1e3$

思路：

直接考虑折扣价不是很好想，所以考虑能不能把这些边单独拿出来。
下面我们假定原边是白边，折扣边是黑边，那么对于每次要输出的，问题就转换成了选$k$条黑边的最小生成树的代价是多少。
显然这是一个$wqs$二分的一个经典问题，我们设这个函数是$f(k)$，这是一个凸函数，我们二分一个值$mid$，之后将所有黑边的权值都加上$mid$，让后跑最小生成树，假设选择了$cnt$条黑边，且总代价是$sum$，那么如果$cnt>=k$的话，显然可以更新$ans=sum-k\ast mid$ ，让后调整一下左右边界即可。
直接跑的话复杂度是$O(nmlognlogn)$的，虽然第二个$log$是最小生成树的，常数很小，但仍是过不了，考虑优化。
考虑每次都有很多无用边，即非树边是无用的，所以直接去掉非树边即可，将边缩小到$O(n)$级别的，但是$n^{2}lognlogn$想过这个有$10$个测试点的题还是不可能的。
继续优化，考虑对于每次二分，他的信息是可以复用的，且边权在$[1,1000]$范围内，所以可以预处理出来，之后每次查询二分的话直接使用已有信息即可。
复杂度$O(n^{2}a+nlogn)$，其中$n^{2}a$的$a$是并查集的常数，很小。

// Problem: J - Road Discount
// Contest: Virtual Judge - 2021多校第三场补题
// URL: https://vjudge.net/contest/449636#problem/J
// Memory Limit: 524 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
//#pragma GCC optimize(2)
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#include<random>
#include<cassert>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].l+tr[u].r)>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std;

//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); }
//void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); }
//void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;

const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f;
const double eps=1e-6;

int n,m;
int p[N],ans,cnt;
PII f[N];
struct Node {
	int x,y,w,add,op;
	bool operator < (const Node &W) const {
		return w<W.w;
	}
}edge1[N],edge2[N],edge[N];

int find(int x) {
	return x==p[x]? x:p[x]=find(p[x]);
}

PII check(int mid) {
	for(int i=1;i<=m;i++) edge2[i].w+=mid;
	int tot=0;
	edge1[m+1].w=INF; edge2[m+1].w=INF;
	for(int i=1,j=1;i<=m||j<=m;) {
		if(edge1[i].w<edge2[j].w) edge[++tot]=edge1[i++];
		else edge[++tot]=edge2[j++];
	}
	cnt=0; ans=0;
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=tot;i++) {
		int a=edge[i].x,b=edge[i].y,w=edge[i].w,op=edge[i].op;
		int pa=find(a),pb=find(b);
		if(pa==pb) continue;
		p[pa]=pb; cnt+=op==0;
		ans+=w;
	}
	for(int i=1;i<=m;i++) edge2[i].w-=mid;
	return {cnt,ans};
}

int main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0);
	
	int _; scanf("%d",&_);
	while(_--) {
		scanf("%d%d",&n,&m);
		for(int i=1;i<=m;i++) scanf("%d%d%d%d",&edge1[i].x,&edge1[i].y,&edge1[i].w,&edge1[i].add),edge1[i].op=1;
		for(int i=1;i<=m;i++) {
			edge2[i]=edge1[i],edge2[i].w=edge1[i].add;
			edge2[i].op=0;
		}
		sort(edge1+1,edge1+1+m); sort(edge2+1,edge2+1+m);
		
		int tot=0;
		for(int i=1;i<=n;i++) p[i]=i;
		for(int i=1;i<=m;i++) {
			int a=edge1[i].x,b=edge1[i].y,w=edge1[i].w,op=edge1[i].op;
			int pa=find(a),pb=find(b);
			if(pa==pb) continue;
			p[pa]=pb; edge1[++tot]=edge1[i];
		}
		tot=0;
		for(int i=1;i<=n;i++) p[i]=i;
		for(int i=1;i<=m;i++) {
			int a=edge2[i].x,b=edge2[i].y,w=edge2[i].w,op=edge2[i].op;
			int pa=find(a),pb=find(b);
			if(pa==pb) continue;
			p[pa]=pb; edge2[++tot]=edge2[i];
		}
		m=n-1;
		
		for(int i=-1010;i<=1010;i++) f[i+1010]=check(i);
		for(int k=0;k<n;k++) {
			int l=-1010,r=1010,res;
			while(l<=r) {
				int mid=(l+r)/2;
				if(f[mid+1010].X>=k) res=f[mid+1010].Y-mid*k,l=mid+1;
				else r=mid-1;
			}
			printf("%d\n",res);
		}
	}



	return 0;
}
/*

*/









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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146