SHARE
TWEET

POTHOLE

a guest Jun 25th, 2019 66 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package _07.POTHOLE
  2.  
  3. import java.util.*
  4.  
  5. fun main() = with(Scanner(System.`in`)) {
  6.     repeat(nextInt()) {
  7.         val chambers = nextInt()
  8.         val cave = Cave(chambers)
  9.         repeat(nextInt()) { cave.makeEntry(nextInt()) }
  10.         for (level in 2 until chambers) repeat(nextInt()) { cave.linkEntries(level, nextInt()) }
  11.         val graph = cave.asBipartiteGraph()
  12. //        println(cave.directPaths + graph.HopcroftKarp())
  13.         println(cave.directPaths + graph.maxBPM())
  14.     }
  15. }
  16.  
  17. class Cave(private val size: Int) {
  18.     var directPaths = 0
  19.     private val corridors = Array(size) { mutableSetOf<Int>() }
  20.     private val exits = mutableListOf<Int>()
  21.  
  22.     fun makeEntry(entry: Int) {
  23.         if (entry != size) {
  24.             corridors[entry].add(entry)
  25.             corridors[1].add(entry)
  26.         } else directPaths++
  27.     }
  28.  
  29.     fun linkEntries(source: Int, target: Int) {
  30.         if (target == size)
  31.             if (corridors[1].contains(source)) directPaths++
  32.             else exits += source
  33.         else corridors[target].addAll(corridors[source])
  34.     }
  35.  
  36.     fun asBipartiteGraph(): BipartiteGraph {
  37.         val graph = BipartiteGraph(size)
  38.         exits.forEach { exit ->
  39.             corridors[exit].forEach { entry ->
  40.                 graph.connect(entry, exit)
  41.             }
  42.         }
  43.         return graph
  44.     }
  45. }
  46.  
  47. class BipartiteGraph(private val size: Int) {
  48.     private val adjacent = Array(size) { mutableListOf<Int>() }
  49. //    private val NULL = 0
  50. //    private val INFINITY = Int.MAX_VALUE
  51.     private val U = mutableSetOf<Int>()
  52.     private val V = mutableSetOf<Int>()
  53. //    private val pair = IntArray(size)
  54. //    private val distance = IntArray(size)
  55.  
  56. //    override fun toString(): String = "U: " + System.lineSeparator() +
  57. //            U.joinToString(System.lineSeparator()) { "$it -> ${adjacent[it]}" } +
  58. //            System.lineSeparator() + "V: " + System.lineSeparator() +
  59. //            V.joinToString(System.lineSeparator()) { "$it -> ${adjacent[it]}" }
  60.  
  61.     private fun BPM(u: Int, visited: BooleanArray, matchR: IntArray): Boolean {
  62.         adjacent[u].filter { !visited[it] }.forEach { v ->
  63.             visited[v] = true
  64.             if (matchR[v] < 0 || BPM(matchR[v], visited, matchR)) {
  65.                 matchR[v] = u
  66.                 return true
  67.             }
  68.         }
  69.         return false
  70.     }
  71.  
  72.     fun maxBPM(): Int {
  73.         val matchR = IntArray(size) { -1 }
  74.         return U.filter { BPM(it, BooleanArray(size), matchR) }.size
  75.     }
  76.  
  77. //    private fun BFS(): Boolean {
  78. //        val queue = ArrayDeque<Int>()
  79. //        U.forEach { u ->
  80. //            if (pair[u] == NULL) {
  81. //                distance[u] = 0
  82. //                queue.addLast(u)
  83. //            } else distance[u] = INFINITY
  84. //        }
  85. //
  86. //        distance[NULL] = INFINITY
  87. //        while (queue.isNotEmpty()) {
  88. //            val u = queue.removeFirst()
  89. //            if (distance[u] < distance[NULL]) {
  90. //                adjacent[u].forEach { v ->
  91. //                    if (distance[pair[v]] == INFINITY) {
  92. //                        distance[pair[v]] = distance[u] + 1
  93. //                        queue.addLast(pair[v])
  94. //                    }
  95. //                }
  96. //            }
  97. //        }
  98. //
  99. //        return distance[NULL] != INFINITY
  100. //    }
  101.  
  102. //    private fun DFS(u: Int): Boolean {
  103. //        if (u != INFINITY) {
  104. //            adjacent[u].forEach { v ->
  105. //                if (distance[pair[v]] == distance[u] + 1 && DFS(pair[v])) {
  106. //                    pair[v] = u
  107. //                    pair[u] = v
  108. //                    return true
  109. //                }
  110. //            }
  111. //            distance[u] = INFINITY
  112. //            return false
  113. //        }
  114. //        return true
  115. //    }
  116.  
  117. //    fun HopcroftKarp(): Int {
  118. //        var result = 0
  119. //        while (BFS()) result += U.filter { pair[it] == 0 && DFS(it) }.size
  120. //        return result
  121. //    }
  122.  
  123.     fun connect(u: Int, v: Int) {
  124.         adjacent[u].add(v)
  125. //        adjacent[v].add(u)
  126.         U += u
  127. //        V += v
  128.     }
  129. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top