自动搬运

查看原文

来自洛谷，原作者为

	OccDreamer 百年如露

搬运于2025-08-24 22:50:30，当前版本为作者最后更新于2023-09-26 19:36:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑每次入队一个点之后这一个点在优先队列中的权值知道它弹出来都不会变化。

怎么利用这个性质呢？

考虑现在如果有 $4$ 个点 $1,2,3,4$，如果我们连边 $(1,2,v_1)$，$(1,3,1)$，$(3,2,1)$，$(3,4,v_2)$，$(2,4,1)$。

其中 $v_1,v_2$ 都是很大的数，且 $v_2 < \dfrac{v_1}{2}$。

那么我们可以做到弹堆顺序为 $1,3,4,2,4$，你会发现在这一个结构中 $4$ 会被弹出两次。

那么如果我们能构造出 $16$ 个这样的结构，那么我们就可以使得弹出次数 $\geq k=10^5$。

类似于上述构造方法构造即可，需要注意下点的弹出顺序之类的。

代码中的 $a,b,c,d$ 可以看做对应一个结构中的 $1,2,3,4$。

//code by Emissary
#include<bits/stdc++.h>

#define fi first
#define se second
#define vc vector
#define db double
#define ll long long
#define mk make_pair
#define pb push_back
#define PI pair<int,int>
#define ull unsigned long long
#define err cerr << "   -_-   " << endl
#define debug cerr << " ------------------- " << endl

#define input(x) freopen(#x".in","r",stdin)
#define output(x) freopen(#x".out","w",stdout)

#define NO puts("No")
#define YES puts("Yes")

//#define int long long

using namespace std;

namespace IO{
	inline int read(){
		int X=0, W=0; char ch=getchar();
		while(!isdigit(ch)) W|=ch=='-', ch=getchar();
		while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
		return W?-X:X;
	}
	inline void write(int x){
		if(x<0) x=-x, putchar('-');
		if(x>9) write(x/10);
		putchar(x%10+'0');
	}
	inline void sprint(int x){write(x), putchar(32);}
	inline void eprint(int x){write(x), putchar(10);}
}using namespace IO;

const int inf = 1e6;

signed main(){
	freopen("SPFA.in","w",stdout);
	cout << 100 << ' ' << 16*5 << endl;
	int las=1, now=1e6;
	for(int i=1;i<=16;++i){
		int a=las, b=a+1, c=b+1, d=c+1;
		now--;
		cout << a << ' ' << b << ' ' << now << endl;
		now>>=1; now-=5;
		cout << a << ' ' << c << ' ' << 1 << endl;
		cout << c << ' ' << b << ' ' << 1 << endl;
		cout << c << ' ' << d << ' ' << now << endl;
		cout << b << ' ' << d << ' ' << 1 << endl;
		las=d;
	}
	return 0;
}