Codeforces 1139E Maximize Mex 二分图匹配
2024-10-12 14:46:14
离线之后把删数变成加数, 然后一边跑匈牙利一遍算答案。
#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 ;
} /*
*/
最新文章
- H5单页面手势滑屏切换原理
- 开发维护大型 Java 项目的建议
- Python中的浅拷贝 深拷贝
- python logging 配置
- Windows7中IIS简单安装与配置(详细图解)
- canvas基本用法
- Sprint Three 回顾与总结&;发表评论&;团队贡献分
- LeetCode Intersection of Two Linked Lists
- Django搭建及源码分析(二)
- NGUI系列教程十(Scroll View实现触摸滚动相册效果)
- SQLSERVER2012用户登录error40
- [T-SQL]从变量与数据类型说起
- JVM之--Java内存结构(第一篇)
- QTableWidget查找指定项(由github处学习到)
- 什么是MemCache
- Nyoj 吝啬的国度(图论&;&;双DFS)
- 王立平--string.Empty
- java-信息安全(四)-数据签名、数字证书
- ubuntu12.04 desktop默认无ssh支持
- FrameBuffer系列 之 一点资源
热门文章
- simulate events
- 解决定位工具报错Error while parsing UI hierarchy XML file: Invalid ui automator hierarchy file.
- 用docker快速搭建wordpress博客
- Struts2框架中使用Servlet的API示例
- Confluence 6 配置 HTTP 超时设置
- react native 打包Ignoring return value of function declared with warn_unused_result attribute
- Nginx详解十九:Nginx深度学习篇之进阶高级模块
- .tar.xz文件的解压方法
- 深入理解 Vue Computed 计算属性
- python修改hosts