网站的绝对路径,网站ui设计学的是什么,app平台需要多少钱,wordpress nextapp传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你一个nnn个点mmm条边的图#xff0c;每个边有一个代价以及折扣价#xff0c;你需要输出nnn行#xff0c;第iii行代表你可以选i−1i-1i−1条边使其变成优惠价#xff0c;问每次的最小生成树的代价是多…传送门
文章目录题意思路题意
给你一个nnn个点mmm条边的图每个边有一个代价以及折扣价你需要输出nnn行第iii行代表你可以选i−1i-1i−1条边使其变成优惠价问每次的最小生成树的代价是多少。 n≤1e3,m≤2e5,ci,di≤1e3n\le 1e3,m\le2e5,c_i,d_i\le 1e3n≤1e3,m≤2e5,ci,di≤1e3
思路
直接考虑折扣价不是很好想所以考虑能不能把这些边单独拿出来。 下面我们假定原边是白边折扣边是黑边那么对于每次要输出的问题就转换成了选kkk条黑边的最小生成树的代价是多少。 显然这是一个wqswqswqs二分的一个经典问题我们设这个函数是f(k)f(k)f(k)这是一个凸函数我们二分一个值midmidmid之后将所有黑边的权值都加上midmidmid让后跑最小生成树假设选择了cntcntcnt条黑边且总代价是sumsumsum那么如果cntkcntkcntk的话显然可以更新anssum−k∗midanssum-k*midanssum−k∗mid 让后调整一下左右边界即可。 直接跑的话复杂度是O(nmlognlogn)O(nmlognlogn)O(nmlognlogn)的虽然第二个logloglog是最小生成树的常数很小但仍是过不了考虑优化。 考虑每次都有很多无用边即非树边是无用的所以直接去掉非树边即可将边缩小到O(n)O(n)O(n)级别的但是n2lognlognn^2lognlognn2lognlogn想过这个有101010个测试点的题还是不可能的。 继续优化考虑对于每次二分他的信息是可以复用的且边权在[1,1000][1,1000][1,1000]范围内所以可以预处理出来之后每次查询二分的话直接使用已有信息即可。 复杂度O(n2anlogn)O(n^2anlogn)O(n2anlogn)其中n2an^2an2a的aaa是并查集的常数很小。
// 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,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#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 pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-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 wW.w;}
}edge1[N],edge2[N],edge[N];int find(int x) {return xp[x]? x:p[x]find(p[x]);
}PII check(int mid) {for(int i1;im;i) edge2[i].wmid;int tot0;edge1[m1].wINF; edge2[m1].wINF;for(int i1,j1;im||jm;) {if(edge1[i].wedge2[j].w) edge[tot]edge1[i];else edge[tot]edge2[j];}cnt0; ans0;for(int i1;in;i) p[i]i;for(int i1;itot;i) {int aedge[i].x,bedge[i].y,wedge[i].w,opedge[i].op;int pafind(a),pbfind(b);if(papb) continue;p[pa]pb; cntop0;answ;}for(int i1;im;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 i1;im;i) scanf(%d%d%d%d,edge1[i].x,edge1[i].y,edge1[i].w,edge1[i].add),edge1[i].op1;for(int i1;im;i) {edge2[i]edge1[i],edge2[i].wedge1[i].add;edge2[i].op0;}sort(edge11,edge11m); sort(edge21,edge21m);int tot0;for(int i1;in;i) p[i]i;for(int i1;im;i) {int aedge1[i].x,bedge1[i].y,wedge1[i].w,opedge1[i].op;int pafind(a),pbfind(b);if(papb) continue;p[pa]pb; edge1[tot]edge1[i];}tot0;for(int i1;in;i) p[i]i;for(int i1;im;i) {int aedge2[i].x,bedge2[i].y,wedge2[i].w,opedge2[i].op;int pafind(a),pbfind(b);if(papb) continue;p[pa]pb; edge2[tot]edge2[i];}mn-1;for(int i-1010;i1010;i) f[i1010]check(i);for(int k0;kn;k) {int l-1010,r1010,res;while(lr) {int mid(lr)/2;if(f[mid1010].Xk) resf[mid1010].Y-mid*k,lmid1;else rmid-1;}printf(%d\n,res);}}return 0;
}
/**/
