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


相关推荐

  • html 转 js_json转html

    html 转 js_json转html/*1.用浏览器内部转换器实现html转码*/functionhtmlEncode(html){//1.首先动态创建一个容器标签元素,如DIVvartemp=document.createElement(“div”);//2.然后将要转换的字符串设置为这个元素的innerText(ie支持…

    2022年9月4日
    5
  • IOC 控制反转[通俗易懂]

    IOC 控制反转[通俗易懂]SpringFramework概述https://blog.csdn.net/centrl/article/details/115519480通过前面的学习,我们至少已经知道IOC,下面我们就来说说IOC是个什么东西。1.写在前面首先来想一件事,作为程序员,怎么开发程序才最巴适?我觉得最起码有两点:开发简单、升级简单。开发简单,就是我们只管写业务逻辑(培养只会写if-else的程序员)。 升级简单,这里也包含两点:我们使用的技术(可理解为框架)出了什么问…

    2022年6月16日
    33
  • 指针的赋值和使用[通俗易懂]

    指针的赋值和使用[通俗易懂]更多来自:http://imcc.blogbus.com3.9.3指针的赋值和使用在得到一个指针变量之后,指针变量的值还是一个随机值。这个值可能是内存中无关紧要的数据,也可能是重要的数据或者程

    2022年7月4日
    27
  • DOS分区表(Boot Sector引导扇区)[通俗易懂]

    DOS分区表(Boot Sector引导扇区)[通俗易懂]>>DOS分区体系的硬盘也叫MBR硬盘,0号扇区是主引导记录MBR,DOS分区体系的硬盘用分区表记录每个分区的类型起始位置和分区的大小。其中,分区表就在0号扇区内,所以0号扇区如果损坏,那么这个硬盘就不能正确识别分区。>>DOS分区的使用范围:windows系统,Linux系统以及基于IA32平台FreeDBS和OpenDBS等操作系统都使用DOS分区体系。&g…

    2022年10月23日
    0
  • matlab根据数据画三维图_matlab导入三组数据画三维图

    matlab根据数据画三维图_matlab导入三组数据画三维图首先先分析对象。将数据利用matlab画出图,最开始是导入数据,然后处理数据,最后将处理的数据画出来。所以我将它分为三个步骤。第一步:导入数据如果是mat数据。可以直接load 如果是txt数据。可以用txtread 如果是excel数据。可以用xlsread详细的,可以参考https://blog.csdn.net/blueskyjian/article/details/728…

    2022年10月11日
    0
  • 借助Unity AR Foundation构建跨平台AR应用

    借助Unity AR Foundation构建跨平台AR应用

    2021年6月19日
    94

发表回复

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

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