UVALive 6525 Attacking rooks 二分匹配 经典题 全栈程序员-站长 • 2022年1月31日 下午9:00 • 未分类 • 阅读 49 UVALive 6525 Attacking rooks 二分匹配 经典题 大家好,又见面了,我是全栈君。 题目链接: <pre name="code" class="cpp">#pragma comment(linker, "/STACK:1024000000,1024000000") #include<bits/stdc++.h> template <class T> inline bool rd(T &ret) { char c; int sgn; if(c=getchar(),c==EOF) return 0; while(c!='-'&&(c<'0'||c>'9')) c=getchar(); sgn=(c=='-')?-1:1; ret=(c=='-')?0:(c-'0'); while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0'); ret*=sgn; return 1; } template <class T> inline void pt(T x) { if (x <0) { putchar('-'); x = -x; } if(x>9) pt(x/10); putchar(x%10+'0'); } using namespace std; const int N = 10105; struct Edge{ int to, nex; }edge[N*2]; int head[N], edgenum; void init(){memset(head, -1, sizeof head); edgenum = 0;} void add(int u, int v){ Edge E = {v, head[u]}; edge[edgenum] = E; head[u] = edgenum++; } int lef[N], pn; int tim, T[N]; bool match(int x){ for(int i=head[x]; ~i; i=edge[i].nex) { int v = edge[i].to; if(T[v] != tim) { T[v] = tim; if(lef[v] == -1 || match( lef[v] )) //match(lef[v]) : 原本连接v的X集点 lef[v] 能不能和别人连。假设能 则v这个点就空出来和x连 { lef[v] = x; return true; } } } return false; } int solve(){ int ans = 0; memset(lef, -1, sizeof(lef)); for(int i = 1; i<= pn; i++)//X集匹配。X集点标号从 1-pn 匹配边是G[左点].size() { tim++; if( match( i ) ) ans++; } return ans; } int n, siz, s[105][105], l[105][105], mp[105][105]; char str[105]; void input(){ siz = n; for(int i = 1; i <= n; i++) { scanf("%s", str+1); for(int j = 1; j <= n; j++){ if(str[j] == 'X') mp[i][j] = ++siz; else mp[i][j] = 0; } } } void build(){ for(int i = 1; i <= n; i++) s[0][i] = i; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(mp[i][j]) s[i][j] = mp[i][j]; else s[i][j] = s[i-1][j]; for(int i = 1; i <= n; i++) l[i][n+1] = i; for(int i = n; i; i--) { for(int j = 1; j <= n; j++) if(mp[j][i]) l[j][i] = mp[j][i]; else l[j][i] = l[j][i+1]; } init(); pn = siz; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(mp[i][j] == 0) add(l[i][j+1], s[i-1][j]); } int main(){ tim = 1; memset(T, 0, sizeof T); while(cin>>n){ input(); build(); cout<<solve()<<endl; } return 0; } /* 5 X.... X.... ..X.. .X... ....X 3 .X. XXX XXX 3 .X. X.X XXX 3 .X. X.X X.X 3 .X. X.X .X. 3 XXX XXX XXX 15 XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX XXXXXXXXXXXXXXX */ 版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请联系我们举报,一经查实,本站将立刻删除。 发布者:全栈程序员-站长,转载请注明出处:https://javaforall.net/115695.html原文链接:https://javaforall.net 赞 (0) 全栈程序员-站长 0 0 生成海报 相关推荐 mysql自定义函数详解_mysqlinterval函数 mysql自定义函数详解_mysqlinterval函数个人博客原文链接更多文章欢迎访问个人博客站点建定义函数的的基本语法如下–DELIMITER是用来设置边界符的DELIMITER//CREATEFUNCTION函数名(形参列表)RETURNS返回类型begin–函数体RETURNEND//DELIMITER;创建日期时间格式化函数DROPFUNCTIONIFEXISTS`FORMAT_DATE_TIME`;CREATE… 全栈程序员-站长 2022年9月7日 0 富文本框_html表单输入框对齐 富文本框_html表单输入框对齐1.HTML代码:<trid="illegal"><th></th><tdcolspan="3"style 全栈程序员-站长 2022年8月2日 5 python实现windows锁定桌面 python实现windows锁定桌面fromctypesimport*user32=windll.LoadLibrary(‘user32.dll’)user32.LockWorkStation() 全栈程序员-站长 2022年7月21日 27 VS2019+OpenCV安装与配置教程 VS2019+OpenCV安装与配置教程目录VS2019的下载安装OpenCV的下载安装OpenCV的配置配置系统变量给VS中的工程一键配置OpenCV测试配置的效果最近要用到很多OpenCV的库,所以开始学了点OpenCV,本文记录VS和OpenCV的安装、配置过程。配置OpenCV使用配置文件的方法,配置完一次就可以给其他工程使用,非常方便。VS2019的下载安装这里有VisualStudio2019的详细教程,社区版是免费使用的,登录一下微软账户就行。OpenCV的下载安装OpenCV下载链接。我装的是4.3、Window 全栈程序员-站长 2022年6月24日 46 计算机技术与阅读,PISA2018阅读素养计算机化自适应测试的技术与方法探析 计算机技术与阅读,PISA2018阅读素养计算机化自适应测试的技术与方法探析原标题:PISA2018阅读素养计算机化自适应测试的技术与方法探析摘要:PISA2018阅读素养的计算机化自适应测试采用核心阶段、阶段1和阶段2的3阶段自适应测试,题库设定有245道题目,组成45个测试单元,并将其组合成若干题组,用于不同阶段的测试。在路径设计上,为避免位置效应问题,除核心阶段→阶段1→阶段2的标准路径之外,还采用核心阶段→阶段2→阶段1的替代路径。PISA2018阅读素养计算机… 全栈程序员-站长 2022年6月5日 25 《剑指offer》– 复杂链表的复制、字符串的排列、数组中出现次数超过一半的数字、连续子数组的最大和 《剑指offer》– 复杂链表的复制、字符串的排列、数组中出现次数超过一半的数字、连续子数组的最大和 全栈程序员-站长 2021年10月3日 38 发表回复您的邮箱地址不会被公开。 必填项已用 * 标注昵称: 邮箱: 网址: 记住昵称、邮箱和网址,下次评论免输入 提交