大致题意:
给出一个n*n的矩阵,每个矩阵元素的U或者是D。
例如
DUD
UDD
DDU
每次操作,可以交换任意两行或者两列。求是否能使得其主对角线上的元素全部变成U。
大致思路:
仔细思考就能发现,问题可以转化为,能否找出n个‘U’,使得他们之间两两的行数和列数都不相同。于是就很容易就能构造出二分匹配模型了。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int nMax=1005;
int n,m;
long long num[nMax];
bool map[nMax][nMax];
bool vis[nMax];
int linkk[nMax];
int dfs(int s){
for(int i=1;i<=m;i++){
if(!vis[i]&&map[s][i]){
vis[i]=1;
if(linkk[i]==-1||dfs(linkk[i])){
linkk[i]=s;
return 1;
}
}
}
return 0;
}
char str[nMax][nMax];
int main(){
int cas,i,j;
while(cin>>n){
m=n;
memset(map,0,sizeof(map));
for(i=1;i<=n;i++)
{
cin>>str[i]+1;
for(j=1;j<=n;j++)
{
if(str[i][j]=='U')
{
map[i][j]=1;
}
}
}
int ans=0;
memset(linkk,-1,sizeof(linkk));
for(i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
if(ans==n)
{
cout<<"YES\n";
}
else{
cout<<"NO\n";
}
}
return 0;
}
分享到:
相关推荐
ZOJ,全称“浙江大学程序在线评测系统”(Zhejiang University Online Judge),是一个提供信息学(算法竞赛)题库及程序评测的网站。以下是关于ZOJ的详细介绍: 一、基本信息 名称:浙江大学程序在线评测系统(ZOJ)...
zoj 2316 Matrix Multiplication.md
浙江大学ZOJ题目分类旨在为编程学习者提供一个系统化的训练平台,帮助他们在算法和编程技能上实现质的飞跃。ZOJ平台提供的分类题目包括但不限于基础算法、数据结构、动态规划以及模拟问题等,这些分类覆盖了计算机...
学习ACM程序设计的朋友一定要看,这是训练必备的POJ ZOJ题目分类及解题思路
3. **算法与数据结构**:700题涵盖的范围广泛,涉及基本的排序算法(如冒泡、快速、归并排序),查找算法(如二分查找),以及高级算法如动态规划(如斐波那契数列、背包问题)、图论(如最短路径、最小生成树)、...
【标题】"ZOJ 1002" 是一个在线编程竞赛题目,源自ZOJ(Zhejiang Online Judge),这是一个面向ACM/ICPC(国际大学生程序设计竞赛)的在线评测系统。题目编号1002,通常表示该题是ZOJ平台上的一个问题,可能涉及算法...
"POJ 计算几何入门题目.doc"可能介绍了计算几何的基础知识,并提供了一些实践题目,这个领域涉及点、线、面的相互关系,以及在二维和三维空间中的几何操作。 5. **ZOJ题目分类**: "zoj题目分类.doc"对应浙江大学...
《ZOJ ACM分类加题解》是针对浙江大学ACM竞赛训练平台的一份宝贵资源,它包含了大量的编程竞赛题目和相应的解答。这份资料旨在帮助参赛者提升算法能力,提高解决实际问题的技巧,无论是在无网络环境下还是有网络时,...
1. **基础算法**:包括排序(如快速排序、归并排序)、搜索(如二分查找)、动态规划、贪心算法、回溯算法等。 2. **高级数据结构**:如链表、树(二叉树、平衡树如AVL和红黑树)、图(深度优先搜索、广度优先搜索...
【标题】"ZOJ1027解题指南"是一个针对特定编程竞赛题目——ZOJ1027的解决方案集合。ZOJ,全称为“Zhejiang Online Judge”,是浙江大学主办的一个在线编程竞赛平台,提供了丰富的算法题目供参赛者练习和挑战。本解题...
3. **字符串处理**:ZOJ题目中往往包含许多字符串处理问题,如模式匹配、字符串比较、最长公共子序列等。源代码会展示如何高效地操作字符串。 4. **数学知识**:部分题目可能需要运用到高等数学知识,如组合数学、...
首先,我们可以从这些源代码中学习到基础的算法思想,如排序算法(快速排序、归并排序、冒泡排序、插入排序等)、搜索算法(二分查找、深度优先搜索、广度优先搜索等)。这些算法是解决问题的基本工具,理解和掌握...
1. **基础算法**:作为入门部分,这个集合可能包括基础数据结构和算法,如排序(快速排序、归并排序、堆排序)、查找(二分查找、哈希表查找)以及图论的基本概念(Dijkstra、Floyd等)。这些是所有ACM竞赛者必须...
9. 排序和搜索:快速排序、归并排序、二分查找等,这些都是算法中的基本操作。 难易度的划分则可能基于题目所需的时间复杂度、空间复杂度、解题思路的复杂性等因素。初级题目通常是基础概念和算法的运用,适合初学...
zoj 题库 详细解答 解题代码 该资源主要涵盖了 zoj 题库中的各种编程题目,涵盖了基本算法、数据结构、数学运算等多个方面的知识点。下面是对该资源中出现的知识点的详细解释: 1. 第一次 ACM 总结(7th ACM) 该...
Problem Arrangement zoj 3777
**ZOJ月赛题解 (ZOJ Monthly, August 2014)** ZOJ(Zhejiang Online Judge)是中国著名的在线编程竞赛平台之一,它为程序员和学生提供了丰富的算法练习和比赛机会。2014年8月的ZOJ月赛是一场面向广大编程爱好者的...
《ZOJ 4041问题的正确解法与程序分析》 ZOJ(Zhejiang Online Judge)是一个知名的在线编程竞赛平台,其中的题目编号为4041的题目吸引了众多程序员的关注。本篇文章将深入探讨ZOJ 4041的正确解法,并对提供的源代码...
【标题】"zoj.zip_zoj"所对应的资源是一个与ZOJ(Zhejiang Online Judge)相关的代码集合。ZOJ是浙江大学主办的一个在线编程竞赛平台,它提供了多种算法题目供用户练习和提交代码进行评测。这个压缩包很可能包含了在...