UVALive 6525 Attacking rooks 二分匹配 经典题

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)
全栈程序员-站长的头像全栈程序员-站长


相关推荐

  • 简述ajax的实现原理_fluidsim实例讲解

    简述ajax的实现原理_fluidsim实例讲解AJAX即“AsynchronousJavascriptAndXML”(异步JavaScript和XML),是指一种创建交互式网页应用的网页开发技术。AJAX是一种用于创建快速动态网页的技术。通过在后台与服务器进行少量数据交换,AJAX可以使网页实现异步更新。这意味着可以在不重新加载整个网页的情况下,对网页的某部分进行更新。解决传统的网页(不使用AJAX)如果需要更新内容,必须重载整个网页页面。

    2022年8月16日
    6
  • linux aarch64启动不了,引导AArch64 Linux

    linux aarch64启动不了,引导AArch64 Linux前注:本文是Documentation/arm64/booting的翻译。这篇文章基于RussellKing所写的《theARMbootingdocument》,并与AArch64Linuxkernel的所有公开版本相关。AArch64异常模型由几级异常组成,分别是EL0-EL3,EL0和EL1又分别有安全和非安全模式,EL2是hypervisor级别,仅存在于安全模式,EL3是最…

    2022年10月16日
    5
  • pytest报错_git查看提交的文件

    pytest报错_git查看提交的文件前言我们每天写完自动化用例后都会提交到git仓库,随着用例的增多,为了保证仓库代码的干净,当有用例新增的时候,我们希望只运行新增的未提交git仓库的用例。pytest-picked插件可以

    2022年7月30日
    6
  • 原生android系统官网 source.android.com,存储  |  Android 开源项目  |  Android Open Source Project…「建议收藏」

    原生android系统官网 source.android.com,存储  |  Android 开源项目  |  Android Open Source Project…「建议收藏」Android一直在不断发展,可支持各种存储设备类型和功能。所有Android版本均支持配有传统存储(包括便携式存储和模拟存储)的设备。便携式存储是指物理介质(如SD卡或USB设备),用于进行临时数据传输/文件存储。物理介质可以随设备一起保留更长时间,但并非固定在设备上,可以移除。自Android1.0开始,SD卡已可用作便携式存储;Android6.0增加了对USB…

    2022年6月19日
    232
  • pthreads php 安装全过程[通俗易懂]

    pthreads php 安装全过程

    2022年2月17日
    35
  • 《哈佛大学公开课:幸福课》 学习笔记(1)

    《哈佛大学公开课:幸福课》 学习笔记(1)视频链接:http://v.163.com/special/sp/positivepsychology.html当初《幸福课》在网易公开课很火,当然现在也很火。但是由于对门户热门内容的成见,再加上一个江湖骗子式的课程名字,我还以为是又一个简单空洞的心灵鸡汤。但是今天看完了第一节课,事实告诉我,真是要相信群众的眼睛呀,而且随便怀疑哈佛出品也未免太过自信。70+分钟的时间内,没有多少废话,反复

    2022年7月18日
    15

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

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