当前位置:   article > 正文

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

多校wqs二分

传送门

文章目录

题意:

给你一个 n n n个点 m m m条边的图,每个边有一个代价以及折扣价,你需要输出 n n n行,第 i i i行代表你可以选 i − 1 i-1 i1条边使其变成优惠价,问每次的最小生成树的代价是多少。
n ≤ 1 e 3 , m ≤ 2 e 5 , c i , d i ≤ 1 e 3 n\le 1e3,m\le2e5,c_i,d_i\le 1e3 n1e3,m2e5,ci,di1e3

思路:

直接考虑折扣价不是很好想,所以考虑能不能把这些边单独拿出来。
下面我们假定原边是白边,折扣边是黑边,那么对于每次要输出的,问题就转换成了选 k k k条黑边的最小生成树的代价是多少。
显然这是一个 w q s wqs wqs二分的一个经典问题,我们设这个函数是 f ( k ) f(k) f(k),这是一个凸函数,我们二分一个值 m i d mid mid,之后将所有黑边的权值都加上 m i d mid mid,让后跑最小生成树,假设选择了 c n t cnt cnt条黑边,且总代价是 s u m sum sum,那么如果 c n t > = k cnt>=k cnt>=k的话,显然可以更新 a n s = s u m − k ∗ m i d ans=sum-k*mid ans=sumkmid ,让后调整一下左右边界即可。
直接跑的话复杂度是 O ( n m l o g n l o g n ) O(nmlognlogn) O(nmlognlogn)的,虽然第二个 l o g log log是最小生成树的,常数很小,但仍是过不了,考虑优化。
考虑每次都有很多无用边,即非树边是无用的,所以直接去掉非树边即可,将边缩小到 O ( n ) O(n) O(n)级别的,但是 n 2 l o g n l o g n n^2lognlogn n2lognlogn想过这个有 10 10 10个测试点的题还是不可能的。
继续优化,考虑对于每次二分,他的信息是可以复用的,且边权在 [ 1 , 1000 ] [1,1000] [1,1000]范围内,所以可以预处理出来,之后每次查询二分的话直接使用已有信息即可。
复杂度 O ( n 2 a + n l o g n ) O(n^2a+nlogn) O(n2a+nlogn),其中 n 2 a n^2a n2a a 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/weixin_40725706/article/detail/436727
推荐阅读
相关标签
  

闽ICP备14008679号