杭电多校-Darnassus-(最小生成树本质+预处理+链式向前星)

Darnassus

题意：
就是给你一个数组全排列，任意两点间的距离是abs(i-j)*abs(p[i]-p[j])。现在问你所有点联通起来的最小花费。n<=40000。

思考：

1. 既然题目就是说让所有点连通的最小花费，那么很容易想到最小生成树，但是那么多点，我如何建边呢？这里建边也没有好建立的方式。然后当时看完就感觉不能写，而且过的人也少，就没看了。
2. 实际上，对于这个题如果我就让1-2-3-4-n这样连接，会发现边权最大也就n-1对吧。也就是在最大边权不超过n-1的情况下，我可以让这个图联通。而最小生成树算法本质是什么？就是边权大小，在边权相同的时候他们地位一样，边权不同的时候，越小越牛逼。
3. 所以如果想要所有点连通的花费更低，那么我建立的边权值大小>n-1的都不要。那么我现在就是找abs(i-j)*abs(p[i]-p[j])<=n-1的所有边，但是这样我好像还要枚举两点求权值看看是否<=n-1啊，这不还是n×n的复杂度？
4. 其实不是，既然是a*b<=c，要么a<=c要么b<=c要么a<=c&&b<=c。所以我可以先枚举a，但是在枚举a的时候，我保证了a<=sqrt(n-1)，所以这个时候枚举的点就是n×sqrt(n)的，然后再看看边权是否<=n-1就可以了。然后我再看看b<=c的情况，那么就是先枚举值p1 p2，但是也保证了b<=c而且p这些值是全排列也是<=n的，所以复杂度是n×sqrt(n)的，然后再看看边权是否<=n-1就可以了。
5. 还要注意的是，把边存完之后，如果再排序的话复杂度是n×sqrt(n)×log(n×sqrt(n))这样就炸了。由于边权都很小，所以不同边权开不同的数组，那么就很容易想到用vector加PII，但是卡这个存图。所以用个链式向前星存就可以了。但是提交还是超时，因为还要加个优化，当连接了n-1条边的时候就break，后面的就不判断了。这样就不超时了。

代码：

#include
#define fi first
#define se second
#define pb push_back
#define db double
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
		
using namespace std;
const int mod = 1e9+7,inf = 1e9;
const int N = 5e4+10,M = 5e7+5;

struct node{
	int a,b,ne;
}e[M];

int T,n,m,k;
int va[N];
int pos[N];
int acc[N];
int h[N],idx;

int add(int a,int b,int c)
{
	e[idx].a = a;
	e[idx].b = b;
	e[idx].ne = h[c];
	h[c] = idx++;
}

int find(int x)
{
	if(acc[x]!=x) acc[x] = find(acc[x]);
	return acc[x];
}

int krukal()
{
	int ans = 0,sum = 0;
	for(int i=0;i<=n-1;i++)
	{
		for(int j=h[i];j!=-1;j=e[j].ne)
		{
			int t1 = find(e[j].a),t2 = find(e[j].b);
			if(t1!=t2)
			{
				acc[t1] = t2;
				ans += i;
				if(++sum>=n-1) break;
			}
		}
		if(sum>=n-1) break;
	}
	return ans;
}

void init()
{
	idx = 0;
	for(int i=0;i<=n;i++)
	{
		h[i] = -1;
		acc[i] = i;
	}
}

signed main()
{
	IOS;
	cin>>T;
	while(T--)
	{
		cin>>n;
		init();
		for(int i=1;i<=n;i++)
		{
			cin>>va[i];
			pos[va[i]] = i;	
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;(i-j)*(i-j)<n&&j<=n;j++)
			{
				int c = abs(i-j)*abs(va[i]-va[j]);
				if(c<n) add(i,j,c);
			}
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=i+1;(i-j)*(i-j)<n&&j<=n;j++)
			{
				int c = abs(i-j)*abs(pos[i]-pos[j]);
				if(c<n) add(pos[i],pos[j],c);
			}
		}
		cout<<krukal()<<"\n";
	}
	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

总结：
多多思考，理解本质。