1587 問題 A: 藍(lán)橋杯算法訓(xùn)練VIP-Buying Sets
時(shí)間限制: 1s
內(nèi)存限制: 128MB 提交: 173 解決: 81
題目描述
給定n個(gè)集合, 要求選出其中某些集合, 使得這些集合的并集的勢, 等于選出的集合的數(shù)目.
對(duì)于任意的k(1< =k< =n), 滿從中選出任意k個(gè)集合, 這k個(gè)集合的并集的勢一定大于等于k.
每個(gè)集合有一個(gè)權(quán)值, 每個(gè)選擇方案的代價(jià)是所選的集合的權(quán)值的和.
請(qǐng)輸出代價(jià)最小的選擇方案的代價(jià).
當(dāng)然, 不選擇任何一個(gè)集合是一個(gè)可行的方案(權(quán)值和為0), 但不一定最優(yōu)(權(quán)值和可以為負(fù)).
輸入
第一行一個(gè)正整數(shù)n(1< =n< =300), 為集合個(gè)數(shù).
在接下來n行中, 第i行描述第i個(gè)集合:
首先給出一個(gè)正整數(shù)m[i]為該集合的勢, 顯然1< =m[i]< =n.
接下來m[i]個(gè)在1到n之間的整數(shù), 表示該集合中的元素.
最后一行n個(gè)整數(shù), 為每個(gè)集合的權(quán)值, 絕對(duì)值不超過1e6.
輸出
僅一個(gè)整數(shù), 為代價(jià)最小的選擇方案的代價(jià).
提示
零基礎(chǔ)同學(xué)可以先學(xué)習(xí)
視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，
點(diǎn)擊這里了解課程詳情