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 相关推荐 velocity中的注释种类 velocity中的注释种类各种编程语言都有相对应的注释 而 velocity 作为一种模板引擎也不例外 大体上 velocity 的主食类型分为如下几类 nbsp 单行注释 nbsp nbsp Thisisasingl nbsp 多行注释 nbsp nbsp nbsp nbsp nbsp Thusbeginsam linecomment Onlinevisito t nbsp nbsp nbsp seethistex 全栈程序员-站长 2026年3月26日 3 字体在ppt中可以整体替换吗_如何批量替换PPT中的字体? 字体在ppt中可以整体替换吗_如何批量替换PPT中的字体?如何批量替换 PPT 中的字体 时间 2016 06 03 来源 网络作者 未知点击 次 PPT 制作技巧 如何批量替换 PPT 中的字体 问题 如何批量替换 PPT 中的字体 解答 其实 PPT 有专门的功能来实现 不过使用此功能前 需要一些细节 具体操作如下 首先如何查看一个 PPT 到底用到了那些字体呢 在 开始 编辑 替换 按钮的下拉处找到 替换字体 下图 1 处 新弹窗口的 Replace 的下拉窗口 可以看到打 全栈程序员-站长 2026年3月17日 1 即梦Ai 即梦ai做建筑效果图 即梦ai做建筑效果图 全栈程序员-站长 2026年3月13日 2 ftp工具哪个好用_客户端游戏人气排行榜 ftp工具哪个好用_客户端游戏人气排行榜序言:随着互联网的不断普及、发展,越来越多的人在使用FTP软件,它被广泛的应用于网页制作、网站更新、资源共享、数据传输等多个方面。“工欲善其事,必先利其器”,面对现在多如牛毛的各种FTP软件,我们到底选择哪一款才能更好的帮助我们呢?为此我们将针对当前比较流行的十款FTP客户端软件进行横向评测,通过下面的评测我们将会给出圆满的答案,希望能够给广大读者提供指引和帮助。导读:☆: 全栈程序员-站长 2022年10月19日 6 pycharm for mac 快捷键整理 pycharm for mac 快捷键整理command D 复制当前行 command delete 删除当前行 shift Enter 快速换行 command 快速注释 nbsp ctrl 加号打开折叠 ctrl 减号关闭折叠 ctrl shift 加号全部折叠 ctrl shift 减号全部展开 command 7 或者点击左下角的 structures 可以查看当前文件中代码的结构 T 全栈程序员-站长 2026年3月27日 3 android 复制控件,Android长按复制文本功能[通俗易懂] android 复制控件,Android长按复制文本功能[通俗易懂]安卓一般能用到长按复制的控件Textview,Editext,可能也有WebView在开始之前先说一个我遇到的一个坑:viewGroup中有一个这个属性android:descendantFocusability=”blocksDescendants”这个属性有三个值:beforeDescendants:viewgroup会优先其子类控件而获取到焦点afterDescendants:viewgro… 全栈程序员-站长 2026年4月13日 7 发表回复您的邮箱地址不会被公开。 必填项已用 * 标注昵称: 邮箱: 网址: 记住昵称、邮箱和网址,下次评论免输入 提交