1. 全栈程序员必看首页

UVALive 6525 Attacking rooks 二分匹配 经典题

全栈程序员-站长 • • 未分类 • 阅读 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
                粉丝
            

        

                        
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
        

    


                        

                    

                
                

                     上一篇
                    2022年1月31日 下午8:00
                

            

                            

                
                

                    下一篇 
                    2022年1月31日 下午9:00
                

            

            

                    



                                            

                            
相关推荐
  • 
        
    
        
            velocity中的注释种类        
            
    
        
    
                
    
            
                                 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中可以整体替换吗_如何批量替换PPT中的字体？如何批量替换 PPT 中的字体 时间 2016 06 03 来源 网络作者 未知点击 次 PPT 制作技巧 如何批量替换 PPT 中的字体 问题 如何批量替换 PPT 中的字体 解答 其实 PPT 有专门的功能来实现 不过使用此功能前 需要一些细节 具体操作如下 首先如何查看一个 PPT 到底用到了那些字体呢 在 开始 编辑 替换 按钮的下拉处找到 替换字体 下图 1 处 新弹窗口的 Replace 的下拉窗口 可以看到打
    
        
    
        
    
                        
    
                                
                    全栈程序员-站长的头像                    全栈程序员-站长
                
            
    
                                    2026年3月17日
            
    
                1            
    
        
    
    
    

    • 

  • 
        
    
        
            即梦ai做建筑效果图        
                即梦Ai
            
    
        
    
                
    
            
                                 即梦ai做建筑效果图            
        
    
        
    
            
    即梦ai做建筑效果图
    
        
    
        
    
                        
    
                                
                    全栈程序员-站长的头像                    全栈程序员-站长
                
            
    
                                    2026年3月13日
            
    
                2            
    
        
    
    
    

    • 

  • 
        
    
        
            ftp工具哪个好用_客户端游戏人气排行榜        
            
    
        
    
                
    
            
                                 ftp工具哪个好用_客户端游戏人气排行榜            
        
    
        
    
            
    ftp工具哪个好用_客户端游戏人气排行榜序言：随着互联网的不断普及、发展，越来越多的人在使用FTP软件，它被广泛的应用于网页制作、网站更新、资源共享、数据传输等多个方面。“工欲善其事，必先利其器”，面对现在多如牛毛的各种FTP软件，我们到底选择哪一款才能更好的帮助我们呢？为此我们将针对当前比较流行的十款FTP客户端软件进行横向评测，通过下面的评测我们将会给出圆满的答案，希望能够给广大读者提供指引和帮助。导读：☆：
    
        
    
        
    
                        
    
                                
                    全栈程序员-站长的头像                    全栈程序员-站长
                
            
    
                                    2022年10月19日
            
    
                6            
    
        
    
    
    

    • 

  • 
        
    
        
            pycharm for mac 快捷键整理        
            
    
        
    
                
    
            
                                 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长按复制文本功能[通俗易懂]            
        
    
        
    
            
    android 复制控件,Android长按复制文本功能[通俗易懂]安卓一般能用到长按复制的控件Textview，Editext，可能也有WebView在开始之前先说一个我遇到的一个坑：viewGroup中有一个这个属性android:descendantFocusability=”blocksDescendants”这个属性有三个值：beforeDescendants：viewgroup会优先其子类控件而获取到焦点afterDescendants：viewgro…
    
        
    
        
    
                        
    
                                
                    全栈程序员-站长的头像                    全栈程序员-站长
                
            
    
                                    2026年4月13日
            
    
                7            
    
        
    
    
    

    • 

                        

                    


    	

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






 


	

		

                

                    

            
    




            

                                                

                                                                                                            

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