费用流(mcmf)
题目描述
给定长度为 n 的非负整数数组 a,以二进制形式描述。你要构造非负整数数组 b,满足 bi≥ai,且对任意 i<j,biANDbj=0。其中 AND 为按位与。
求最小的 ∑i=1nbi。
输入格式
从标准输入读取数据。第一行正整数 n。接下来 n 行,第 i 行先给出 ki,再给出 ki 个数 xi,1,…,xi,ki,表示 ai=∑j=1ki2xi,j−1。
输出格式
在标准输出中输出一行,表示最小和的二进制表示,不带前导零。
样例 1
输入
2
1 1
2 1 2
输出
101
解释
a=[1,3],可取 b=[1,4],总和为 5。
样例 2
输入
4
2 1 2
1 1
5 4 5 6 7 9
2 1 8
输出
111111111
解释
可取 b=[4,1,376,130]。
数据范围
令 M=∑ixi,ki,X=maxixi,ki。1≤n,M≤106,ki≥1,1≤xi,1<⋯<xi,ki。
| 子任务 |
n≤ |
X≤ |
M≤ |
特殊约束 |
分值 |
| 1 |
2 |
105 |
105 |
无 |
10 |
| 2 |
1000 |
A |
9 |
| 3 |
105 |
105 |
10 |
| 4 |
5 |
无 |
8 |
| 5 |
105 |
11 |
| 6 |
50 |
2500 |
| 7 |
1000 |
105 |
12 |
| 8 |
105 |
14 |
| 9 |
106 |
15 |
特殊性质 A:所有 ki=1。每个子任务内的所有测试点均通过,才能得到该组分数。