POJ–2289–Jamie's Contact Groups【二分图的多个匹配+二分法答案】

全栈程序员-站长 • 2022年1月9日上午11:00 • 未分类 • 阅读 43

POJ–2289–Jamie's Contact Groups【二分图的多个匹配+二分法答案】

大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。

链接：#include<cstring> #include<string> #include<fstream> #include<sstream> #include<iostream> #include<iomanip> #include<cstdio> #include<cctype> #include<algorithm> #include<queue> #include<map> #include<set> #include<vector> #include<stack> #include<ctime> #include<cstdlib> #include<functional> #include<cmath> using namespace std; #define PI acos(-1.0) #define MAXN 500010 #define eps 1e-6 #define INF 0x7FFFFFFF #define LLINF 0x7FFFFFFFFFFFFFFF #define seed 131 #define MOD 1000000007 #define ll long long #define ull unsigned ll #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 const int M=2010; int bmap[M][M]; //下标0開始 bool bmask[M]; int nx,ny; int vcy[M]; int cy[M][M]; int limit; //多重匹配限制 bool findpath(int u){ int i,j; for(i = 0; i < ny; i++){ if(bmap[u][i] && !bmask[i]){ bmask[i] = 1; if(vcy[i] < limit){ cy[i][vcy[i]++] = u; return 1; } for(j = 0; j < vcy[i]; j++){ if(findpath(cy[i][j])){ cy[i][j] = u; return 1; } } } } return 0; } bool MulMatch(){ memset(vcy,0,sizeof(vcy)); for(int i=0; i < nx; i++){ memset(bmask,0,sizeof(bmask)); if(!findpath(i)) return 0; } return 1; } char str[5000]; int main(){ int i,j,x; while(scanf("%d%d",&nx,&ny),nx||ny){ memset(bmap,0,sizeof(bmap)); for(i = 0; i < nx; i++){ scanf("%s", str); gets(str); stringstream sin(str); while(sin >> x){ bmap[i][x] = 1; } } int l = 0, r = nx; while(l < r){ limit = (l + r) / 2; if(MulMatch()) r = limit; else l = limit + 1; } printf("%d\n", r); } return 0; }

版权声明：本文博客原创文章，博客，未经同意，不得转载。

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/117199.html原文链接：https://javaforall.net

全栈程序员-站长

0 0

linux防火墙(firewall、iptable)

linux防火墙(firewall、iptable)一、iptables防火墙1、基本操作#查看防火墙状态serviceiptablesstatus#停止防火墙serviceiptablesstop#启动防火墙serviceiptablesstart#重启防火墙serviceiptablesrestart#永久关闭防火墙chkconfigiptablesoff…

全栈程序员-站长
2022年5月28日
39
kernel: TCP: time wait bucket table overflow的问题剖析及解决方法

kernel: TCP: time wait bucket table overflow的问题剖析及解决方法随着访问量的增大，系统默认的承受能力达到上限，这个时候就会报一些异常。比如/var/log/messages中常见的“kernel:TCP:timewaitbuckettableoverflow”这个信息，本文介绍问题的来源及解决办法。

全栈程序员-站长
2022年6月10日
33
pycharm下载插件_SiteD 插件中心

pycharm下载插件_SiteD 插件中心我使用的PyCharm软件的版本：2016.1.4参考网站：https://www.jetbrains.com/help/pycharm/2016.1/installing-updating-and-uninstalling-repository-plugins.html给PyCharm软件添加plugins的图文操作（这里以添加Markdown插件）Step1.启动PyC

全栈程序员-站长
2022年8月26日
5
idea

idea2022.01.12激活码永久[最新免费获取]2022.03.02

(idea2022.01.12激活码永久)这是一篇idea技术相关文章，由全栈君为大家提供，主要知识点是关于2021JetBrains全家桶永久激活码的内容https://javaforall.net/100143.htmlIntelliJ2021最新激活注册码，破解教程可免费永久激活，亲测有效，上面是详细链接哦~40ZKSWCX8G-eyJsaWNlb…

全栈程序员-站长
2022年4月2日
60
公共 DNS server IP 地址

公共 DNS server IP 地址

全栈程序员-站长
2021年12月5日
68
最小二乘法正规方程推导过程

最小二乘法正规方程推导过程最小二乘法正规方程推导过程线性回归岭回归：添加L2L_2L2正则项输入样本X∈Rm×n\textbf{X}\in\mathbb{R}^{m\timesn}X∈Rm×n，输出y∈Rm×1\textbf{y}\in\mathbb{R}^{m\times1}y∈Rm×1，需要学习的参数w∈Rn×1\textbf{w}\in\mathbb{R}^{n\times1}w∈Rn×1。其中，mmm为样本个数，nnn为单个样本维度。线性回归最小化目标函数J(w)=12∥y−Xw∥22J(\

全栈程序员-站长
2022年5月16日
45

发表回复

关注全栈程序员社区公众号