Advertisement
Guest User

Untitled

a guest
Mar 19th, 2019
102
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Go 2.61 KB | None | 0 0
  1. package main
  2.  
  3. import (
  4.     "container/heap"
  5.     "fmt"
  6.     "math"
  7.     "time"
  8.  
  9.     "github.com/skorobogatov/input"
  10. )
  11.  
  12. type Vertex struct {
  13.     x, y int
  14. }
  15.  
  16. type Edge struct {
  17.     a, b            *setItem
  18.     priority, index int
  19. }
  20.  
  21. type setItem struct {
  22.     parent     *setItem
  23.     x          *Vertex
  24.     val, depth int
  25. }
  26.  
  27. type PriorityQueue []*Edge
  28.  
  29. func (pq PriorityQueue) Len() int { return len(pq) }
  30.  
  31. func (pq PriorityQueue) Less(i, j int) bool {
  32.     return pq[i].priority < pq[j].priority
  33. }
  34.  
  35. func (pq PriorityQueue) Swap(i, j int) {
  36.     pq[i], pq[j] = pq[j], pq[i]
  37.     pq[i].index = i
  38.     pq[j].index = j
  39. }
  40.  
  41. func (pq *PriorityQueue) Push(x interface{}) {
  42.     n := len(*pq)
  43.     item := x.(*Edge)
  44.     item.index = n
  45.     *pq = append(*pq, item)
  46. }
  47.  
  48. func (pq *PriorityQueue) Pop() interface{} {
  49.     old := *pq
  50.     n := len(old)
  51.     item := old[n-1]
  52.     item.index = -1
  53.     *pq = old[0 : n-1]
  54.     return item
  55. }
  56.  
  57. func makeSet(x *Vertex) *setItem {
  58.     t := new(setItem)
  59.     t.x = x
  60.     t.parent = t
  61.     t.depth = 0
  62.     return t
  63. }
  64.  
  65. func find(x *setItem) *setItem {
  66.     if x.parent == x {
  67.         return x
  68.     } else {
  69.         x.parent = find(x.parent)
  70.         return x.parent
  71.     }
  72. }
  73.  
  74. func union(x *setItem, y *setItem) {
  75.     rootY := find(y)
  76.     rootX := find(x)
  77.     if rootX.depth < rootY.depth {
  78.         rootX.parent = rootY
  79.     } else {
  80.         rootY.parent = rootX
  81.         if rootX.depth == rootY.depth && rootX != rootY {
  82.             rootX.depth++
  83.         }
  84.     }
  85. }
  86.  
  87. func main() {
  88.     start := time.Now()
  89.     var n, a, b int
  90.     input.Scanf("%d", &n)
  91.     points := make([](*Vertex), n)
  92.     for i := 0; i < n; i++ {
  93.         input.Scanf("%d%d", &a, &b)
  94.         points[i] = &Vertex{a, b}
  95.     }
  96.     pq := make(PriorityQueue, (n*n-n)/2)
  97.  
  98.     BuildGraph(points, &pq)
  99.     heap.Init(&pq)
  100.     //heap.Init(&pq)
  101.     fmt.Printf("%.2f\n", spanningTree(n, &pq))
  102.     end := time.Now()
  103.     fmt.Println(end.Sub(start))
  104. }
  105.  
  106. func BuildGraph(pointsArr [](*Vertex), pq *PriorityQueue) {
  107.     n := len(pointsArr)
  108.     set := make([](*setItem), n)
  109.     for i, val := range pointsArr {
  110.         set[i] = makeSet(val)
  111.     }
  112.     cnt := 0
  113.     for i := 0; i < n; i++ {
  114.         for j := i + 1; j < n; j++ {
  115.             if i == j {
  116.                 continue
  117.             }
  118.             a := ((pointsArr[j].x) - (pointsArr[i].x))
  119.             b := ((pointsArr[j].y) - (pointsArr[i].y))
  120.             dist := ((a * a) + (b * b))
  121.             (*pq)[cnt] = &Edge{set[i], set[j], dist, -1}
  122.             //heap.Push(pq, &Edge{set[i], set[j], dist, -1})
  123.             cnt++
  124.         }
  125.     }
  126. }
  127.  
  128. func spanningTree(n int, edges *PriorityQueue) float64 {
  129.     totalDist := 0.0
  130.     m := len(*edges)
  131.     cnt := 0
  132.     for i := 0; i < m && cnt < (n-1); i++ {
  133.         elem := (heap.Pop(edges).(*Edge))
  134.         if find(elem.a) != find(elem.b) {
  135.             totalDist += math.Sqrt((float64)(elem.priority))
  136.             cnt++
  137.             union(elem.a, elem.b)
  138.         }
  139.     }
  140.     return totalDist
  141. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement