GGAutomaton's Blog
0%

基站建设

发表于 分类于 ，

可以发现所有合法的建站方案，都是两个有且只有一条公共边的三元环拼在一起。题目转化为枚举三元环。
这里给出一种 \(O(m\sqrt{m})\) 的方法。
将所有点分成两类：度大于等于 \(\sqrt{m}\) 的点称为大点，小于 \(\sqrt{m}\) 的点称为小点。
1.枚举三个大点能否组成三元环。
2.枚举小点，以及和它相邻的两个点，能否组成三元环。
判断两点之间有无连边需要使用哈希。

复杂度证明：
1.大点数目不超过 \(\sqrt{m}\) ，枚举复杂度 \(O(\sqrt{m}^3)\)
2.设小点有b条边和它相连。枚举复杂度约为 \(O(\frac{m}{b} b^2)\)
另外可以证明 \(\sqrt{m}\) 是大点小点的最优临界。
上述两步的复杂度都是 \(O(m\sqrt{m})\) 。

也算一道模板题了。个人比较懒，哈希不写判重，冲突就去买彩票

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
#include<iostream>
#include<cstdio>
#include<cmath>
#define Pair pair<int,int>
#define mp(x,y) make_pair(x,y)
#define rint register int
using namespace std;
typedef long long LL;
const int P=1e7+7;
struct node {
	int u,v,ID;
} edge[200005];
int head[50005],vet[400005],nxt[400005],idn[400005],num;
int ha[(int)(1e7+10)];
int bp[50005];
int val[50005],deg[50005],bs;
Pair mx[200005][2];
int n,m;
inline void addedge(int &x,int &y,int &i) {
	num++;vet[num]=y;idn[num]=i;nxt[num]=head[x];head[x]=num;
	num++;vet[num]=x;idn[num]=i;nxt[num]=head[y];head[y]=num;
}
inline int gethash(int &x,int &y) {
	return ((LL)x*(n+1)+y)%P;
}
inline void update(int &v,int &i) {
	if (val[v]>mx[i][0].first && v!=mx[i][0].second) {
		mx[i][1]=mx[i][0];
		mx[i][0]=mp(val[v],v);
	}
	else if (val[v]>mx[i][1].first && v!=mx[i][0].second) mx[i][1]=mp(val[v],v);
}
int main() {
	scanf("%d%d",&n,&m);bs=(int)sqrt((double)m);
	for (rint i=1;i<=n;i++) scanf("%d",&val[i]);
	for (rint i=1;i<=m;i++) {
		int x,y;
		scanf("%d%d",&x,&y);edge[i]=(node){x,y,i};
		addedge(x,y,i);deg[x]++;deg[y]++;
		ha[gethash(x,y)]=ha[gethash(y,x)]=i;
	}
	for (rint i=1;i<=n;i++) if (deg[i]>=bs) bp[++bp[0]]=i;
	for (rint i=3;i<=bp[0];i++) {
		for (rint j=2;j<i;j++) {
			if (ha[gethash(bp[i],bp[j])]==0) continue;
			for (rint k=1;k<j;k++) {
				rint x=ha[gethash(bp[i],bp[j])],y=ha[gethash(bp[i],bp[k])],z=ha[gethash(bp[j],bp[k])];
				if (y==0 || z==0) continue;
				update(bp[i],z);update(bp[j],y);update(bp[k],x);
			}
		}
	}
	for (rint i=1;i<=n;i++) {
		if (deg[i]>=bs) continue;
		for (rint e1=head[i];e1;e1=nxt[e1]) {
			for (rint e2=head[i];e2!=e1;e2=nxt[e2]) {
				rint j=vet[e1],k=vet[e2],x=ha[gethash(j,k)];
				if (x==0) continue;
				update(i,x);update(j,idn[e2]);update(k,idn[e1]);
			}
		}
	}
	int ans=0;
	for (rint i=1;i<=m;i++) {
		if (mx[i][1].second==0) continue;
		ans=max(ans,(val[edge[i].u]+1)*(val[edge[i].v]+1)+mx[i][0].first*mx[i][1].first);
	}
	printf("%d\n",ans);
	return 0;
}