Maximize Mex

离线之后把删数变成加数, 然后一边跑匈牙利一遍算答案。

#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ull unsigned long long using namespace std; const int N = + ;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const int mod = ;
const double eps = 1e-;
const double PI = acos(-); int n, m;
int p[N], c[N];
int d, match[N];
bool vis[N];
bool ban[N]; vector<int> person;
vector<int> G[N];
vector<int> ans; int path(int u) {
for(auto& v : G[u]) {
if(!vis[v]) {
vis[v] = true;
if(match[v] == - || path(match[v])) {
match[v] = u;
return ;
}
}
}
return ;
} int main() {
memset(match, -, sizeof(match));
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++) scanf("%d", &p[i]);
for(int i = ; i <= n; i++) scanf("%d", &c[i]);
scanf("%d", &d);
for(int i = ; i <= d; i++) {
int who; scanf("%d", &who);
ban[who] = true;
person.push_back(who);
}
for(int i = ; i <= n; i++) {
if(ban[i]) continue;
G[p[i]].push_back(c[i]);
}
for(int i = SZ(person) - , j = ; i >= ; i--) {
while() {
memset(vis, , sizeof(vis));
if(path(j)) j++;
else break;
}
int x = person[i];
ans.push_back(j);
G[p[x]].push_back(c[x]);
}
reverse(ans.begin(), ans.end());
for(auto& x : ans) printf("%d\n", x);
return ;
} /*
*/

最新文章

  1. H5单页面手势滑屏切换原理
  2. 开发维护大型 Java 项目的建议
  3. Python中的浅拷贝 深拷贝
  4. python logging 配置
  5. Windows7中IIS简单安装与配置(详细图解)
  6. canvas基本用法
  7. Sprint Three 回顾与总结&amp;发表评论&amp;团队贡献分
  8. LeetCode Intersection of Two Linked Lists
  9. Django搭建及源码分析(二)
  10. NGUI系列教程十(Scroll View实现触摸滚动相册效果)
  11. SQLSERVER2012用户登录error40
  12. [T-SQL]从变量与数据类型说起
  13. JVM之--Java内存结构(第一篇)
  14. QTableWidget查找指定项(由github处学习到)
  15. 什么是MemCache
  16. Nyoj 吝啬的国度(图论&amp;&amp;双DFS)
  17. 王立平--string.Empty
  18. java-信息安全(四)-数据签名、数字证书
  19. ubuntu12.04 desktop默认无ssh支持
  20. FrameBuffer系列 之 一点资源

热门文章

  1. simulate events
  2. 解决定位工具报错Error while parsing UI hierarchy XML file: Invalid ui automator hierarchy file.
  3. 用docker快速搭建wordpress博客
  4. Struts2框架中使用Servlet的API示例
  5. Confluence 6 配置 HTTP 超时设置
  6. react native 打包Ignoring return value of function declared with warn_unused_result attribute
  7. Nginx详解十九:Nginx深度学习篇之进阶高级模块
  8. .tar.xz文件的解压方法
  9. 深入理解 Vue Computed 计算属性
  10. python修改hosts