PCMS Web Client
ИнформацияРезультатыОтправитьРешенияВопросыФайлыВыход
Исходный код
Q.kt
import java.io.*
import java.util.*
import kotlin.*

class Decomposition {
    val NAME = "matching"
    val inputFileName = NAME + ".in"
    val outputFileName = NAME + ".out"
    val MAXN = 1010

    var graph = ArrayList<ArrayList<Int>>()
    var used = BooleanArray(MAXN, {index -> false})
    var p = ArrayList<Pair<Int, Int>>()

    fun dfs(key: Int): Boolean {
        if (used[key])
            return false
        used[key] = true
        for (i in graph[key]) {
            val index = i
            if (p[index].second == -1 || dfs(p[index].second)) {
                p[key] = Pair(index, p[key].second)
                p[index] = Pair(p[index].first, key)
                return true
            }
        }
        return false
    }
    private fun solution(sIn: FastScanner, sOut: PrintWriter) {
        val n = sIn.nextInt()
        val w = ArrayList<Pair<Int, Int>>()
        for (i in 0..n - 1)
            w.add(Pair(0, 0))
        for (i in 0..n - 1)
            w.add(Pair(sIn.nextInt(), i))
        Collections.sort(w) {
            x, y ->
            if (x.first == y.first)
                y.second - x.second
            else
                y.first - x.first
        }
        for (i in 0..n - 1) {
            val m = sIn.nextInt()
            graph.add(ArrayList<Int>())
            p.add(Pair(-1, -1))
            for (j in 0..m - 1)
                graph[i].add(sIn.nextInt() - 1)
        }
        for (i in 0..n - 1){
            for (j in 0..n - 1)
                used[j] = false
            dfs(w[i].second)
        }

        for (i in 0..n - 1)
            sOut.print("" + (p[i].first + 1) + " ")
    }

    fun run() {
        FastScanner(inputFileName).use { sIn ->
            PrintWriter(outputFileName).use { sOut ->
                solution(sIn, sOut)
            }
        }
    }

    private class FastScanner : Closeable {
        private val bufferedReader: BufferedReader
        private var stringTokenizer: StringTokenizer

        constructor(inputStream: InputStream) {
            bufferedReader = BufferedReader(InputStreamReader(inputStream))
            stringTokenizer = StringTokenizer(bufferedReader.readLine())
        }

        constructor(file: File) : this(FileInputStream(file))

        constructor(fileName: String) : this(File(fileName))

        override fun close() {
            bufferedReader.close()
        }

        fun hasNext(): Boolean {
            while (!stringTokenizer.hasMoreTokens()) {
                stringTokenizer = StringTokenizer(bufferedReader.readLine())
            }
            return stringTokenizer.hasMoreTokens()
        }

        fun next(): String? {
            if (hasNext())
                return stringTokenizer.nextToken()
            return null
        }

        fun nextInt(): Int {
            return next()?.toInt()!!
        }

        /*fun nextDouble(): Double {
            return next()?.toDouble()!!
        }

        fun nextLong(): Long {
            return next()?.toLong()!!
        }*/
    }
}


fun main(vararg args: String) {
    Decomposition().run()
}