codeforces 277 A. Learning Languages

2015年12月5日 0 作者 CrazyKK

http://codeforces.com/contest/277/problem/A

题意:有n个人,每个人会一定数目的语言(可能为0),一个人学一门语言的代价为1,人和人之间沟通可以通过任意个中间人翻译。问最少的代价使得这n个人可以相互沟通。

思路:建图方式如下:第i个人会语言j,那么连上i和j+n。然后跑一遍dfs,使得1..n这n个点都被访问过。

结果wa4…觉得算法没问题。。看了官方题解。。发现果然有情况没有考虑到。如果所有的人都什么语言都不会的话,那么答案是不能-1的。。因为。。语言和语言之间不能连边。。改了之后A了。。有点开心。。