AcWing 376. 机器任务
2021/7/14 6:05:07
本文主要是介绍AcWing 376. 机器任务,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接
考察:二分图匹配
思路:
对于每个\(a[i],b[i]\)连接边,需要选择最少的点,覆盖所有的边.
对于二分图匹配问题,每个点只能枚举一次.
Code
#include <iostream> #include <cstring> #include <set> using namespace std; typedef pair<int,int> PII; const int N = 110,K = 1010; int h[N<<1],idx,k,A[K],g[2][N],match[N<<1],n,m; bool st[N<<1]; set<int> s; struct Road{ int to,ne; }road[K<<1]; void add(int a,int b) { road[idx].to = b,road[idx].ne = h[a],h[a] = idx++; } bool dfs(int u) { for(int i=h[u];~i;i=road[i].ne) { int v = road[i].to; if(st[v]) continue; st[v] = 1; if(match[v]==-1||dfs(match[v])) { match[v] = u; return 1; } } return 0; } int main() { // freopen("in.txt","r",stdin); while(scanf("%d%d%d",&n,&m,&k)!=EOF&&n) { idx = 0; memset(h,-1,sizeof h); memset(match,-1,sizeof match); memset(g,0,sizeof g); int tot = 0; s.clear(); for(int j=1;j<=k;j++) { int i,a,b; scanf("%d%d%d",&i,&a,&b); if(!a||!b) continue; if(!g[0][a]) g[0][a] = ++tot; if(!g[1][b]) g[1][b] = ++tot; s.insert(g[0][a]); add(g[0][a],g[1][b]),add(g[1][b],g[0][a]); } int ans = 0; for(auto i:s) { memset(st,0,sizeof st); if(dfs(i)) ans++; } printf("%d\n",ans); } return 0; }
这篇关于AcWing 376. 机器任务的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-23DevExpress 怎么实现右键菜单(Context Menu)显示中文?-icode9专业技术文章分享
- 2024-12-22怎么通过控制台去看我的页面渲染的内容在哪个文件中呢-icode9专业技术文章分享
- 2024-12-22el-tabs 组件只被引用了一次,但有时会渲染两次是什么原因?-icode9专业技术文章分享
- 2024-12-22wordpress有哪些好的安全插件?-icode9专业技术文章分享
- 2024-12-22wordpress如何查看系统有哪些cron任务?-icode9专业技术文章分享
- 2024-12-21Svg Sprite Icon教程:轻松入门与应用指南
- 2024-12-20Excel数据导出实战:新手必学的简单教程
- 2024-12-20RBAC的权限实战:新手入门教程
- 2024-12-20Svg Sprite Icon实战:从入门到上手的全面指南
- 2024-12-20LCD1602显示模块详解