HDU 3605 Escape

  • 2018-08-21
  • 26
  • 0

Description:

2012 If this is the end of the world how to do? I do not know how. But now scientists have found that some stars, who can live, but some people do not fit to live some of the planet. Now scientists want your help, is to determine what all of people can live in these planets.

Input:

More set of test data, the beginning of each data is n (1 <= n <= 100000), m (1 <= m <= 10) n indicate there n people on the earth, m representatives m planet, planet and people labels are from 0. Here are n lines, each line represents a suitable living conditions of people, each row has m digits, the ith digits is 1, said that a person is fit to live in the ith-planet, or is 0 for this person is not suitable for living in the ith planet.
The last line has m digits, the ith digit ai indicates the ith planet can contain ai people most..
0 <= ai <= 100000

Output:

Determine whether all people can live up to these stars
If you can output YES, otherwise output NO.

Sample Input:

1 1
1
1

2 2
1 0
1 0
1 1

Sample Output:

YES
NO

题目链接

由于这道题目的N数据范围很大,直接建图跑最大流会超时,所以要对N进行压缩。

每个人的选择情况由0和1组成,最长也不过10位,所以每个人的选择最多有1024种情况,将这些情况中的0和1所组成的数列看为一个二进制数,这时选择相同的人可以等价,将源点与2^m个数字(即2^m种选择情况)建立流量为选择这种情况的人数的边,再将2^m个数字与m个星球建立流量为无穷大的边,最后将星球与汇点建立流量为星球承载量的边,判断源点至汇点的最大流和人数关系即可。

AC代码:

评论

还没有任何评论,你来说两句吧