bzoj#P4788. [CERC2016] Bipartite Blanket
[CERC2016] Bipartite Blanket
题目描述
在二分图中,所有点被划分成了两个不相交的集合 和 ,每条边都恰好连接着某个 和某个 。一个匹配是一个边集,满足没有任何两条边有相同的端点。我们称一个匹配 覆盖了点集 当且仅当 中的每个点都是 中至少一条边的端点。
给定一个二分图,每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。
给定一个参数 ,请统计有多少点集 ,满足 的权值不小于 ,且 被至少一个匹配 覆盖。
输入格式
第一行包含两个正整数 ,分别表示 集合的点数和 集合的点数。
接下来 行,每行 个 01
字符,其中第 行第 列为 表示 和 之间有一条边。
接下来一行包含 个正整数 ,分别表示 中每个点的权值。
接下来一行包含 个正整数 ,分别表示 中每个点的权值。
最后一行包含一个正整数 ,表示参数 。
输出格式
输出一行一个整数,即满足条件的点集个数。
3 3
010
111
010
1 2 3
8 5 13
21
3
数据规模与约定
对于 的数据,,,。