UVALive 6525 Attacking rooks 二分匹配 经典题 全栈程序员-站长 • 2022年1月31日 下午9:00 • 未分类 • 阅读 55 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 关于作者 全栈程序员-站长 关注 133.5K 文章 3 粉丝 本网站汇聚当前互联网主流语音,持续更新,欢迎关注公众号“全栈程序员社区” Git使用之基于SSH的Gitserver的client配置(下篇)[通俗易懂] 上一篇 2022年1月31日 下午8:00 HTML, CSS学习笔记(完整版)[通俗易懂] 下一篇 2022年1月31日 下午9:00 相关推荐 Java的输入输出语句_c语言有没有输入输出语句 Java的输入输出语句_c语言有没有输入输出语句一、概述 输入输出可以说是计算机的基本功能。作为一种语言体系,java中主要按照流(stream)的模式来实现。其中数据的流向是按照计算机的方向确定的,流入计算机的数据流叫做输入流(inputStream),由计算机发出的数据流叫做输出流(outputStream)。Java语言体系中,对数据流的主要操作都封装在java.io包中,通过java.io包中的类可以实现计算机对数据的输入、输出操作… 全栈程序员-站长 2022年4月19日 41 Mac 读写NTFS硬盘 Mac 读写NTFS硬盘查看磁盘DeviceNode:【diskutilinfo磁盘路径】diskutilinfo/Volumes/CPBA_X64FRE_ZH-CN_DV5通过DeviceNode卸载磁盘:【sudoumount/dev/disk2s1】… 全栈程序员-站长 2022年6月18日 26 mysql中联合索引abc 使用bac_mysql 联合索引 mysql中联合索引abc 使用bac_mysql 联合索引mysql联合索引详解联合索引又叫复合索引。对于复合索引:Mysql从左到右的使用索引中的字段,一个查询可以只使用索引中的一部份,但只能是最左侧部分。例如索引是keyindex(a,b,c).可以支持a|a,b|a,b,c3种组合进行查找,但不支持b,c进行查找.当最左侧字段是常量引用时,索引就十分有效。两个或更多个列上的索引被称作复合索引。利用索引中的附加列,您可以缩小搜索的… 全栈程序员-站长 2022年5月24日 63 Agent 养“龙虾”热潮下 “卫士虾” 上线保护隐私安全 养“龙虾”热潮下 “卫士虾” 上线保护隐私安全 Ai探索者 2026年3月14日 2 linux系添加路由,Linux添加路由的两种方法「建议收藏」 linux系添加路由,Linux添加路由的两种方法「建议收藏」Linux中增加软路由的两种方法第一种:routeadd-net172.16.6.0netmask255.255.255.0gw172.16.2.254deveth0/*增加一条网络172.16.6.0/24经过172.16.2.254eth0*//*-net增加网络-host增加主机netmask子网掩码gw网关dev装置,设备,这里是你的网卡名*/ro… 全栈程序员-站长 2022年10月5日 5 LinearGradient线性渲染 LinearGradient线性渲染 全栈程序员-站长 2021年12月17日 42 发表回复您的邮箱地址不会被公开。 必填项已用 * 标注昵称: 邮箱: 网址: 记住昵称、邮箱和网址,下次评论免输入 提交