A. Access Levels

题意

有 n 个程序员，m 个文档。

给定一个 n×m 的矩阵 a，其中 aij=1 表示程序员 i 可以访问文档 j，否则不行。

现在我们需要选择一个数字 k，使得总共有 k 个access group。

然后将每个文档放入这 k 个access group中的一个，并且给这个文档设定一个权限值 ci。

然后给每个程序员设定 k 个数字 vi，代表这个程序员在使用第 i 个group时拥有 vi 的权限值。

当一个程序员在访问一个文档 i 时，如果这个文档所在的group为 j，那么需要保证这个程序员的 vj≥ci 才能访问，否则不能。

求一个最小的 k，使得访问矩阵可以被满足，并且给出具体方案。

其中，n,m≤500。

题解

注意到 group 与 group 之间是独立的，因为每个文档仅能属于一个group，所以我们分 group 来考虑。

注意到，如果一个group内有 d 个文档 i1,i2,…,id，那么这些文档对于程序员们来说一定遵循：访问关系为单调为超集。

举个例子，在第二个样例中

copy
1
2
3
2 3
101
100

那么假设这三个文档都在同一个group内，那么按照列来看，就可以得到 11, 00, 10 这三个数字，可以发现 11 > 10 > 00（这里的 11 > 10 是指 11 为 10 的超集）。

这说明这三个文档可以在同一个group内。

这让我们想到了什么？如果我们将每一列看作一个 bitmask，那么如果 b1>b2 则可以由 b1 向 b2 连一条边，这就是一个DAG中的最小路径覆盖问题，每个路径就是一个 group。

剩下的就是很麻烦的实现了，注意去重之类的问题。

代码
copy
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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e2+5;
int n, m;
char a[maxn][maxn];
map<string, int> mask_to_idx;
string masks[maxn];
// return 1 if b < a (b is subset of a)
bool is_sub(string& a, string& b) {
    for (int i = 1; i <= n; i++) {
        if (a[i-1] < b[i-1]) return 0;
    }
    return 1;
}
int par[maxn];
int finds(int u) {
    if (par[u] == u) return u;
    return par[u] = finds(par[u]);
}
void unions(int u, int v) {
    u = finds(u), v = finds(v);
    if (u == v) return;
    par[v] = u;
}
vector<int> adj[maxn<<1];
int vis[maxn<<1], visid = 0, match[maxn<<1], from[maxn<<1];
bool dfs(int u) {
    for (int v : adj[u]) {
        if (vis[v] == visid) continue;
        vis[v] = visid;
        if (!match[v] || dfs(match[v])) {
            match[v] = u;
            return 1;
        }
    }
    return 0;
}
int groupid = 0;
vector<int> groups[maxn];
int belongs[maxn];
int pri[maxn][maxn];  // privilege for the users
int privilege[maxn];  // privilege for each software
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        string s; cin >> s;
        for (int j = 1; j <= m; j++) {
            a[i][j] = s[j-1];
        }
    }
    int id = 0;
    for (int j = 1; j <= m; j++) {
        string mask = "";
        for (int i = 1; i <= n; i++) {
            mask += a[i][j];
        }
        mask_to_idx[mask] = ++id;
        masks[id] = mask;
    }
    for (int i = 1; i <= m; i++) par[i] = i;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == j) continue;
            if (masks[i] == masks[j]) {
                unions(i, j);
            }
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= m; j++) {
            if (i == j) continue;
            if (par[i] == i && par[j] == j && is_sub(masks[i], masks[j])) {
                adj[i].push_back(j+m);
            }
        }
    }
    // 最小路径覆盖
    int ans = 0;  // 记录有多少个独立的parent
    for (int i = 1; i <= m; i++) {
        if (par[i] == i) ans++;
    }
    for (int i = 1; i <= m; i++) {
        if (par[i] == i) {
            visid++;
            ans -= dfs(i);
        }
    }
    for (int i = m+1; i <= 2*m; i++) {
        if (par[i-m] == i-m) {
            if (match[i]) {
                from[match[i]] = i-m;
            }
        }
    }
    for (int i = m+1; i <= 2*m; i++) {
        if (par[i-m] == i-m) {
            if (!match[i]) {
                int j = i-m;
                groupid++;
                while (j) {
                    groups[groupid].push_back(j);
                    belongs[j] = groupid;
                    j = from[j];
                }
            }
        }
    }
    cout << groupid << "\n";
    for (int i = 1; i <= m; i++) {
        belongs[i] = belongs[finds(i)];
        cout << belongs[i] << " ";
    }
    cout << "\n";
    // 已经找到了每个column所在的group
    for (int g = 1; g <= groupid; g++) {
        // 现在处理第 g 个group
        vector<pair<string, int>> vec;  // vector of masks for each user (with selected column in this group)
        for (int i = 1; i <= n; i++) {
            string mask = "";
            for (int j : groups[g]) {
                mask += a[i][j];
            }
            vec.push_back({mask, i});
        }
        sort(vec.begin(), vec.end());
        reverse(vec.begin(), vec.end());
        int pre_pri = 505;
        // 先处理 vec[0]
        
        string s = vec[0].first;  // 长度为 groups[g] 的长度
        pri[vec[0].second][g] = pre_pri - 1;
        for (int k = 0; k < groups[g].size(); k++)  {
            int j = groups[g][k];
            
            if (s[k] == '0') {
                privilege[j] = pre_pri;
            } 
        }
        for (int i = 1; i < n; i++) {
            s = vec[i].first;
            if (s == vec[i-1].first) {  // 如果和前面一个一样，直接复制
                pri[vec[i].second][g] = pri[vec[i-1].second][g];
            } else {
                pre_pri--;
                for (int k = 0; k < groups[g].size(); k++)  {
                    int j = groups[g][k];
                    if (!privilege[j] && s[k] == '0') {
                        privilege[j] = pre_pri;
                    }
                }
                pri[vec[i].second][g] = pre_pri - 1;
            }
        }
        for (int j : groups[g]) {
            if (!privilege[j]) privilege[j] = 1;
        }
    }
    // output answer
    for (int i = 1; i <= m; i++) {
        if (privilege[i] == 0) {
            privilege[i] = privilege[finds(i)];
        }
        cout << (privilege[i]) << " ";
    }
    cout << "\n";
    for (int i = 1; i <= n; i++) {
        for (int g = 1; g <= groupid; g++) {
            cout << pri[i][g] << " ";
        }
        cout << "\n";
    }
}