HBC24608排列游戏[USACO 2011 Ope S]Learning Languages题解

上官魅算法基础篇 2023-11-21 21:14:01 47 0

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

Farmer John's N (2

Farmer John's N (2 <= N <= 10,000) cows, conveniently numbered 1..N, are fluent in some M (1 <= M <= 30,000) languages, also conveniently numbered from 1..M. Cow i can speak in K_i K i (1 <= K_i K i <= M) languages, namely L_{i_1}, L_{i_2},..., L_{i_{K_i}} L i 1 ,L i 2 ,...,L i K i (1 <= L_{i_j} L i j <= M). FJ's cows aren't THAT smart, so the sum of K_i K i over all cows i is at most 100,000. Two cows can't directly talk to each other unless both speak a common language. However, cows can pass messages along, translating if necessary. In other words, cows A and B can have a conversation if and only if there exists a sequence of cows T_1, T_2, ..., T_k T 1 ,T 2 ,...,T k such that A and T_1 T 1 share a language, T_1 T 1 and T_2 T 2 share a language, etc., and T_k T k and B share a language. Farmer John wishes that his cows could be even more social, so he wants all his cows to be able to socialize with any other cow. He can buy books to teach any one of his cows any language he pleases. Being a fairly frugal farmer, FJ wants to purchase the minimum number of books necessary to enable all of his cows to speak to each other. Help him determine: * The minimum number of books he must purchase * Any set of books assigned to cows in any order which will help him meet this goal; a program will grade your output. By way of example, suppose there are three cows named Alberta, Bessie, and Contessa along with three languages denoted as #1, #2, and #3. Alberta can speak languages #2 and #3, Bessie can speak language #2, and Contessa can speak language #1. Currently, Alberta and Bessie can talk to each other, but Contessa is left alone. #1 #2 #3 Alberta x x Bessie x Contessa x FJ wants to fix this situation, so he can buy Contessa a book to teach her language #2. This will ensure all cows speak the same language, so they can all communicate with one another. Note that an alternate solution exists: instead, FJ could buy Contessa a book to teach her language #3. Not all cows would speak the same language, but this would still be a valid solution because Contessa could communicate through Alberta (who also speaks language #3) if she wants to talk to Bessie. Other alternatives exist, and any valid alternate solution will also be accepted.