题面
题目链接
大秦 为你打开 题目传送门
备用题面
在二分图中，所有点被划分成了两个不相交的集合 $A$ 和 $B$ ，每条边都恰好连接着某个 $A$ 和某个 $B$ 。一个匹配是一个边集，满足没有任何两条边有相同的端点。我们称一个匹配 $M$ （不一定是最大匹配）覆盖了点集 $V$ 当且仅当 $V$ 中的每个点都是M中至少一条边的端点。
给定一个二分图，每个点有一个正整数权值。定义一个点集的权值为其中所有点的权值之和。
给定一个参数 $t$ ，请统计有多少点集 $V$ ，满足 $V$ 的权值不小于 $t$ ，且 $V$ 被至少一个匹配 $M$ 覆盖。
思路
考虑当前合法的一个点集s，如果他合法，那么一定有一个完备匹配的点集包含这个点集，也就是两边都满足hall定理的话这两边拼起来的点集也满足要求
所以分别状压两边点集用hall定理转移判断当前点集是否合法，然后分别对两边点集的权值和排个序双指针扫一下计算答案即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 20000010;
int n, m, t;
int E[3][30];
int v[3][30];
int U;
int w[3][N];
int c[3][N];
vector<int >r[3];
inline void Input() {
read(n, m);
int x;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
scanf("%1d", &x);
E[1][i] |= x << (j - 1);
E[2][j] |= x << (i - 1);
}
}
for(int i = 1; i <= n; i++) {
read(v[1][i]);
}
for(int i = 1; i <= m; i++) {
read(v[2][i]);
}
read(t);
}
inline void Find(int op) {
for(int s = 0; s <= U; s++) {
for(int i = 1; i <= n; i++) {
if(!(s & (1 << (i - 1)))) continue;
w[op][s] += v[op][i];
c[op][s] |= E[op][i];
}
c[op][s] = (__builtin_popcount(c[op][s]) >= __builtin_popcount(s));
}
for(int i = 1; i <= n; i++) {
for(int s = 0; s <= U; s++) {
if(!(s & (1 << (i - 1)))) continue;
c[op][s] = min(c[op][s], c[op][s ^ (1 << (i - 1))]);
}
}
}
inline void Work() {
U = (1 << (n = max(n, m))) - 1;
Find(1), Find(2);
for(int s = 0; s <= U; s++) {
if(c[1][s]) r[1].push_back(w[1][s]);
if(c[2][s]) r[2].push_back(w[2][s]);
}
sort(r[1].begin(), r[1].end());
sort(r[2].begin(), r[2].end());
int j = r[2].size();
ll ans = 0;
for(int i = 0; i < r[1].size(); i++) {
while(j > 0 && r[2][j - 1] + r[1][i] >= t) j--;
ans += r[2].size() - j;
}
printf("%lld\n", ans);
}
int main() {
Input();
Work();
return 0;
}
|
