http://codeforces.com/contest/1510
题意：给定n个长度为d的01串，一个初始全为 0 的串S，要S的对于1到d每个位置按照一定顺序置为1，使得对于每个01串，存在某一时刻S等于该串，‘R’ 操作可以将S串全部置0，要求给出最短的操作序列。
最小路径覆盖+贪心
每个01串作为一个节点，若 u 为 v 的子集，则 u，v 连边，每有一条路径就相当于有一个 ’R‘ 操作，则问题变为最小化 路径数+每条路径的代价。一条路径的代价等于这条路径上最大的点包含的 1 的个数，这个最大的点一定是这条路径的一个端点。
最小路径覆盖要转化为二分图匹配。匈牙利算法就是每次尝试把新点加入匹配，要注意只会调节已配对的对象，而不会减少已配对的个数。
又因为一定是从含 1 多的点开始更优（含1多的总是能走到含1少的），所以把所有点按照包含 1 的个数排序后，贪心地从大到小遍历尝试加入匹配。
最后输出路径。
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
| #include <bits/stdc++.h>
#define debug(x) cout << #x << ":\t" << (x) << endl;
using namespace std;
#define ll long long
#define ull unsigned ll
const int N = 2e6 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 100019;
const ll inv2 = (mod + 1) / 2;
int d, n, a[N];
char s[N];
vector<int>G[N];
bool used[N], hd[N];
int match[N];
bool dfs(int u) {
used[u] = 1;
for (int v : G[u]) {
int w = match[v];
if (!w || !used[w] && dfs(w)) {
match[u] = v;
match[v] = u;
return true;
}
}
return false;
}
int cnt(int x) {
int ans = 0;
while (x) {
ans += (x & 1);
x >>= 1;
}
return ans;
}
stack<int>st;
bool cmp(int x, int y) {
return cnt(x) > cnt(y);
}
int main() {
scanf("%d%d", &d, &n);
for (int i = 1; i <= n; i++) {
scanf("%s", s);
for (int j = 0; j < d; j++)a[i] = a[i] * 2 + s[j] - '0';
}
sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i] > a[j] && (a[i] & a[j]) == a[j]) {
G[i + n].push_back(j);
G[j].push_back(i + n);
}
}
}
int ans = -1;
for (int i = 1; i <= n; i++) {
if (!match[i]) {
fill(used, used + n + 1, 0);
if (!dfs(i) || i == 1) {
hd[i] = 1;
ans += cnt(a[i]) + 1;
}
}
}
printf("%d\n", ans);
for (int i = 1; i <= n; i++) {
if (!hd[i])continue;
int p = a[i], u = i, v;
st.push(-1);
while (u) {
v = match[u + n];
if (v > n)v -= n;
for (int j = 0; j < d; j++) {
if ((a[u] >> j & 1) != (a[v] >> j & 1))st.push(d - 1 - j);
}
u = v;
}
}
while (st.size() > 1) {
if (st.top() == -1)printf("R ");
else printf("%d ", st.top());
st.pop();
}
puts("");
return 0;
}
|
