-
Notifications
You must be signed in to change notification settings - Fork 502
/
f.go
91 lines (85 loc) · 1.69 KB
/
f.go
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
package main
import (
"sort"
)
func maxWeight(edges [][]int, values []int) (ans int) {
quickSelect := func(a []int, k int) []int {
if k >= len(a)-1 {
return a
}
for l, r := 0, len(a)-1; l < r; {
v := a[l]
i, j := l, r+1
for {
for i++; i < r && a[i] < v; i++ {
}
for j--; j > l && a[j] > v; j-- {
}
if i >= j {
break
}
a[i], a[j] = a[j], a[i]
}
a[l], a[j] = a[j], v
if j == k {
break
} else if j < k {
l = j + 1
} else {
r = j - 1
}
}
return a[:k+1]
}
// 边按照权值从大到小排序
sort.Slice(edges, func(i, j int) bool { a, b := edges[i], edges[j]; return values[a[0]]+values[a[1]] > values[b[0]]+values[b[1]] })
g := make([]map[int]int, len(values))
for i := range g {
g[i] = map[int]int{}
}
for i, e := range edges {
v, w := e[0], e[1]
g[v][w] = i + 1
g[w][v] = i + 1
}
for i, m := range g {
// 找所有能和 i 组成三角形的边
es := []int{}
if len(m)*len(m) > len(edges) {
// 度数大于 √E,枚举所有边
for j, e := range edges {
if m[e[0]] > 0 && m[e[1]] > 0 {
es = append(es, j)
}
}
} else {
// 否则,枚举相邻的点
for v := range m {
for w := range m {
if eid := g[v][w]; eid > 0 {
es = append(es, eid-1)
}
}
}
}
// 找到权值最大的三条边,对每条边,枚举另一条边
top3 := quickSelect(es, 2)
for _, eid := range top3 {
e := edges[eid]
v, w := e[0], e[1]
sum := values[i] + values[v] + values[w]
for _, eid := range es {
s := sum
for _, u := range edges[eid] {
if u != v && u != w {
s += values[u]
}
}
if s > ans {
ans = s
}
}
}
}
return
}