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-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享
- 2024-04-14stopped 状态设置为变量,由外部传递进来-icode9专业技术文章分享
- 2024-04-14为什么ansible执行远程脚本需要放到后台-icode9专业技术文章分享
- 2024-04-14shell 正则判断字符串内是否含有th-icode9专业技术文章分享