1. 全栈程序员必看首页

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

全栈程序员-用户IM • • 未分类

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; }

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

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

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

【正版授权，激活自己账号】： Jetbrains全家桶Ide使用，1年售后保障，每天仅需1毛

【官方授权 正版激活】： 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0


相关推荐

  • windows 开机自动登录并锁定「建议收藏」

    windows 开机自动登录并锁定「建议收藏」

    windows 开机自动登录并锁定「建议收藏」首先来看看系统启动自动登录的设置：　　按住Win键，再按R键(Win+R)，启动”运行”窗口;　　WindowsXP/2003/2008/2008R2输入”controluserpasswords2″(不含引号)回车;　　Windows7输入”netplwiz”(不含引号)，回车;　　在”用户帐户”-“用户”界面中，取消”要使用本机，用户必须输入用户名和密码(E)”复选框;　　按”确定”按钮

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年7月21日
  • 免费高清第二波！12个无版权限制的大图特供网站

    免费高清第二波！12个无版权限制的大图特供网站

    免费高清第二波！12个无版权限制的大图特供网站推荐:cyRotel2014/08/21in酷站推荐更多22上次优设分享了10个高清无码图库后，竟然有同学评论下回复好人一生平安，盛怒之下，小编意犹未尽马不停蹄精挑细选了这15个大图网站，质量上乘，看着舒服，不担心眼睛。用着舒心，不担心侵权。看入迷了，也不用紧张，永久免费下载。就是这么棒棒哒！对了，上次那篇右戳：《免费高清！10个无版权限制的大图特供…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年7月11日
  • c语言逻辑运算符和逻辑表达式_逻辑运算符与或非

    c语言逻辑运算符和逻辑表达式_逻辑运算符与或非

    c语言逻辑运算符和逻辑表达式_逻辑运算符与或非1．逻辑运算符及其运算规则（1）C语言提供三种逻辑运算符：&amp;amp;amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp;amp;amp;逻辑与（相当于&amp;amp;amp;amp;amp;amp;quot;同时&amp;amp;amp;amp;amp;amp;quot;）||逻辑或（相当于&amp;amp;amp;amp;amp;amp;quot;或者&amp;amp;amp

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月22日
  • haxm intel庐_如何开启Intel HAXM功能「建议收藏」

    haxm intel庐_如何开启Intel HAXM功能「建议收藏」

    haxm intel庐_如何开启Intel HAXM功能「建议收藏」1.启用BIOS中的Intel(R)VirtualizationTechnology选项2.设置成功后，在控制台中输入scqueryintelhaxm。出现下图即为成功3.启动androidSDK，在Extras目录的最下边，勾选IntelHAXM项，并下载4.下载完成后,打开目录:Sdk\extras\intel\Hardware_Accelerated_Execution_…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年6月28日
  • 1100000/1011模二除法_四位数除以两位数的除法算式

    1100000/1011模二除法_四位数除以两位数的除法算式

    1100000/1011模二除法_四位数除以两位数的除法算式原题链接这里所谓的“光棍”，并不是指单身汪啦~ 说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，111111就可以被13整除。 现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算，输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数 ——

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年8月9日
  • 创建可以ssh的docker容器[通俗易懂] docker

    创建可以ssh的docker容器[通俗易懂]

    创建可以ssh的docker容器

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年3月2日

发表回复

您的电子邮箱地址不会被公开。

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