Full Binary Tree

https://code.google.com/codejam/contest/2984486/dashboard#s=p1&a=1

 

题目可以归纳为以下几点：

1. 给定一棵树，节点从1到N标记，用连接节点的无向边（N - 1条）定义， 比如：

3
2 1
1 3

2. 判断这棵树是否是Full Binary Tree, （除了叶节点，其他的节点必须有两个子节点）；

3. 如果不是，需要删除多少个节点（删除节点，以此节点为端点的边也会被删除），可以得到一颗FBT。求最少需要删除几个节点。

 

我自己可以想到的一个比较直观的想法，就是判断现在剩下的节点是否可以组成一颗ＦＢＴ，如果可以，那么到目前为止删除的就是答案；如果不可以，从这些剩下的节点里再删除一个节点，递归判断，并取最小的结果；经过一点优化，可以解决ｓｍａｌｌ　ｐｒａｃｔｉｃｅ；这个算法也就是题目分析里面提到的Ｂｒｕｔｅ　Ｆｏｒｃｅhttps://code.google.com/codejam/contest/2984486/dashboard#s=a&a=1

 

下面是这个算法的实现：

import scala.io.Source

object FullBinaryTree extends App {

  val file = "src/scala/codejam/year2014/round/a/B-small-practice.in"

  val lines = Source.fromFile(file).getLines()

  val T = lines.next().toInt

  def process(t: Int): Unit =
    if (t <= T) {

      val n = lines.next().toInt

      val nodes = (1 to n).foldLeft(Nil: List[Int])((l, x) => x :: l)

      def readEdges(i: Int, edges: List[Edge]): List[Edge] =
        if (i >= n) edges
        else {
          val line = lines.next().split("\\s+").map(_.toInt)
          val x = line(0)
          val y = line(1)
          readEdges(i + 1, Edge(x, y) :: edges)
        }

      val edges = readEdges(1, Nil)

      var cache = Map.empty[String, Int]

      def check(nodes: List[Int], edges: List[Edge], removed: Int): Int = {
        val key = nodes.sorted.mkString("")
        if (cache.contains(key)) {
          cache(key)
        } else {
          val g = new G(nodes, edges)
          val result =
            if (g.isBalance) removed
            else {
              nodes.foldLeft(Integer.MAX_VALUE)((x, n) => {
                val y = check(nodes.filter(_ != n), edges.filterNot(e => e.v == n || e.w == n), removed + 1)
                if (x > y) y
                else x
              })
            }
          cache += (key -> result)
          result
        }
      }

      val removed = check(nodes, edges, 0)

      println(s"Case #$t: $removed")

      process(t + 1)
    }

  process(1)
}

case class Edge(v: Int, w: Int) {
  def other(x: Int) = if (x == v) w else if (x == w) v else throw new Error(s"$x is not a end of this edge")
}

class G(nodes: List[Int], edges: List[Edge]) {
  lazy val degree = nodes.foldLeft(Map.empty[Int, Int])((map, x) => map + (x -> edges.filter(e => e.v == x || e.w == x).size))
  def isBalance =
    if (nodes.size == 1) true
    else {
      val root = degree.filter(x => x._2 == 2)
      edges.size == nodes.size - 1 && root.size == 1 && degree.filter(_ != root.head).forall(x => x._2 == 1 || x._2 == 3)
    }
}

 

那个ｃａｃｈｅ的使用是程序ｐｅｒｆｏｒｍａｎｃｅ的一个关键，否则程序对于某个ｎｏｄｅ　ｌｉｓｔ重复计算很多次；

我一开始判断ｉｓＢａｌａｎｃｅ的方法也要复杂一些，相当于要构建一棵树。看了题目自己的分析后改成了现在这样。