翻译中有一句话:校长将会从每个社团中各选出一个人。
就是一些人被分为一组,从每组中选一些人出来。
这就很容易想到通过二分图的匹配。
\(\text{mex}\) 运算有一个显而易见的贪心:枚举每个值能否被匹配,第一个找不到的值就是答案。
由于 \(\text{mex}\) 运算的值域与 \(n\) 同级,就可以从这方面入手。
我们从每个能力值 \(p_i\) 向社团 \(c_i\) 建边。
假如枚举的值为 \(i\),与增广路算法相似,如果 \(i\) 能再找到匹配,那么 \(\text{mex}\) 的值一定会大于 \(i\),否则就找到了 \(\text{mex}\) 运算的答案。
但如果是这样的话,外层需要枚举到 \(d\),内层要枚举到最大值 \(V\),再加上匈牙利算法的单次的时间复杂度 \({\mathcal{O}}(m)\),就会使总时间复杂度高达 \(\mathcal{O}(dmV)\),当然会 TLE。
考虑优化。
突然感觉与这道题很像,都是枚举值域,然后匹配。
于是就想到了一个玄学优化:用时间戳来优化常数。
在 CF 上交了一次,应该是数据太水,还过了。
代码:
const int N = 5e3, inf = 1e9 + 7;
int n, m, now, D, T;
int c[N + 5], p[N + 5], d[N + 5];
int mat[N + 5], vis[N + 5];
int cnt, head[N + 5];
struct Edge {
int v, ti, nxt;
} e[N + 5];
void add(int u, int v, int ti) {
e[++cnt].nxt = head[u];
e[cnt].v = v;
e[cnt].ti = ti;
head[u] = cnt;
}
bool dfs(int x) {
for (int i = head[x]; i; i = e[i].nxt)
if (e[i].ti > T && vis[e[i].v] != now) {
vis[e[i].v] = now;
if (mat[e[i].v] == -1 || dfs(mat[e[i].v])) { mat[e[i].v] = x; return 1; }
}
return 0;
}
int main() {
n = read(), m = read();
int W = 0;
for (int i = 1; i <= n; i++) p[i] = read(), W = max(W, p[i]);
for (int i = 1; i <= n; i++) c[i] = read();
D = read();
for (int i = 0; i <= n; i++) d[i] = inf; // 初始化到 n。
for (int i = 1; i <= D; i++) d[read()] = i;
for (int i = 1; i <= n; i++) add(p[i], c[i], d[i]);
for (int i = 1; i <= D; i++) {
T = i;
for (int j = 0; j <= m; j++) vis[j] = mat[j] = -1; // mat[j] 的值可能为 0 (p[i] == 0)
bool flag = 0;
for (int j = 0; j <= W; j++) {
now = j;
if (!dfs(j)) {
printf("%d\n", j);
flag = 1;
break;
}
}
if (!flag) printf("%d\n", W + 1);
}
return 0;
}
这样卡一下应该还是不能过,时间复杂度还是没有变。
发现答案肯定是单调不增的,于是倒序枚举,就用一个 \(ans\) 数组记录一下答案,输出即可。
时间复杂度 \({\mathcal{O}}(md)\)
核心代码:
for (int i = D; i; i--) {
T = i;
for (int j = 0; j <= m; j++) vis[j] = 0;
while (dfs(tot)) { // 答案是具有单调性的。
tot++;
for (int j = 0; j <= m; j++) vis[j] = 0;
}
ans[i] = tot;
}
标签:cnt,CF1139E,int,题解,复杂度,枚举,text,Maximize,ti
From: https://www.cnblogs.com/Pengzt/p/17746035.html