二分图：把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。
二分图一般可以处理一些冲突问题，算法不难，但建边有的题会比较复杂。
如果更详细地划分的话，还可以分为门消失和门不消失两种。
小杉家族r个人正在一片空地上散步，突然，外星人来了……
现在请你安排一种方案，使脱逃的小杉尽可能的多。
每组测试数据的
第一行有三个整数r和a和`t(0
第二行有a对实数，第i对数表示第i个传送点的坐标，这些坐标绝对值均不超过1e6。
接下来r行，每行有三个实数x,y,v，表示第i个小杉的坐标和奔跑的速度
对每组测试数据输出一行
仅有一个整数s表示最多有多少个小杉能成功脱逃
Youaregiventhefloorplanofaroomandmustfindouthowmuchtimeitwilltakeforeveryonetogetout.Roomsconsistofobstaclesandwalls,whicharerepresentedonthemapbyan'X',emptysquares,representedbya'.'andexitdoors,whicharerepresentedbya'D'.Theboundaryoftheroomconsistsonlyofdoorsandwalls,andtherearenodoorsinsidetheroom.Theinterioroftheroomcontainsatleastoneemptysquare.
Initially,thereisonepersononeveryemptysquareintheroomandthesepersonsshouldmovetoadoortoexit.TheycanmoveonesquarepersecondtotheNorth,South,EastorWest.Whileevacuating,multiplepersonscanbeonasinglesquare.Thedoorsarenarrow,however,andonlyonepersoncanleavethroughadoorpersecond.
WhatistheminimaltimenecessarytoevacuateeverybodyApersonisevacuatedatthemomentheorsheentersadoorsquare.
Thefirstlineoftheinputcontainsasinglenumber:thenumberoftestcasestofollow.Eachtestcasehasthefollowingformat:OnelinewithtwointegersYandX,separatedbyasinglespace,satisfying3<=Y,X<=12:thesizeoftheroomYlineswithXcharacters,eachcharacterbeingeither'X','.',or'D':avaliddescriptionofaroom
Foreverytestcaseintheinput,theoutputshouldcontainasinglelinewiththeminimalevacuationtimeinseconds,ifevacuationispossible,or"impossible",ifitisnot.
其实这一道题和题库里外星人那一道题解法大致雷同，只是建边的方式有点不同，我们对比着来说
首先，外星人那一道题就是一个简单的两点之间距离公式求出最短路
但是这一道题肯定是不可以直接用公式的，因为题中会有墙
所以我们要用一个bfs预处理出每一个人到每一扇门的最短路
还有一个更大的不同点就是门的性质
在外星人那一道题中，一个人经过了一扇门后，门就会消失，而这一道题经过一扇门后，门不会消失
所以一扇门可以使用多次，但不能被多个人同时使用
所以我们考虑把一个门拆成若干个小门，每一个门代表一个时刻
我们从0时刻开始枚举，把0时刻每一个人可以到达的门和这个人连一条边
如果0时刻不能匹配成功，我们就把1时刻每一个人可以到达的门和这个人连一条边
以此类推，直到所有的时刻都枚举完毕
那么最大的时刻是多少呢
其中\(m\)为房间的长度，\(n\)为房间的宽度
如果最后不能匹配成功，人就不能逃生成功
感性地理解一下，就是一个人被一圈墙围在中间
最后，人数为0的情况下要特判，不特判就会输出'impossible'
最后，我们再来讨论一下复杂度的问题
bfs最坏的情况下就是\(12\times12\times(12\times12+12\times24)=62208\)
没什么影响
建边更是可以忽略不计
其实最主要的开销还是在匈牙利上
最坏的情况\(144\)个点，248832条边，总的复杂度为\(35831808\)
但是这样的强度是达不到的，因为你不可能门有144个，人也有144个，所以实际上是可行的
因为不二分的话，只跑一次匈牙利就可以，用二分的话，可能要跑多次
或者是有更好的二分方法我没有想到
现在电视台有一种节目叫做超级英雄,大概的流程就是每位选手到台上回答主持人的几个问题,然后根据回答问题的多少获得不同数目的奖品或奖金。
主持人问题准备了若干道题目，只有当选手正确回答一道题后，才能进入下一题，否则就被淘汰。为了增加节目的趣味性并适当降低难度，主持人总提供给选手几个“锦囊妙计”，比如求助现场观众，或者去掉若干个错误答案（选择题）等等。
这里，我们把规则稍微改变一下。假设主持人总共有m道题，选手有n种不同的“锦囊妙计”。主持人规定，每道题都可以从两种“锦囊妙计”中选择一种，而每种“锦囊妙计”只能用一次。我们又假设一道题使用了它允许的锦囊妙计后，就一定能正确回答，顺利进入下一题。
现在我来到了节目现场，可是我实在是太笨了，以至于一道题也不会做，每道题只好借助使用“锦囊妙计”来通过。如果我事先就知道了每道题能够使用哪两种“锦囊妙计”，那么你能告诉我怎样选择才能通过最多的题数吗？
输入文件的一行是两个正整数n和m(0 以下的m行，每行两个数，分别表示第m个问题可以使用的“锦囊妙计”的编号。 注意，每种编号的“锦囊妙计”只能使用一次，同一个问题的两个“锦囊妙计”可能一样。 第一行为最多能通过的题数p 56322003043232样例输出4分析比较裸的板子，将每一道题和这一道题能够使用的锦囊妙计建一条边，然后从小到大枚举跑最大匹配，只要有一道题不能匹配，就跳出循环，这也是闯关问题一个独特的地方。 输入的第一行是一个整数N，表示lxhgww拥有N种装备接下来N行，是对这N种装备的描述，每行2个数字，表示第i种装备的2个属性值 输出一行，包括1个数字，表示lxhgww最多能连续攻击的次数。 3123245 2 【数据范围】对于30%的数据，保证N<=1000对于100%的数据，保证N<=1000000 对于第\(i\)件装备，我们把它和它的两个属性建边，最后从小到大枚举一遍伤害 要注意的是，你不能枚举到\(n\)，应该枚举到\(n+1\) 这样做思想是正确的，但是会T掉 所以尽量还是用并查集来做 #include 贝茜想驾驶她的飞船穿过危险的小行星群．小行星群是一个的网格(1≤N≤500)，在网格内有K个小行星(1≤K≤10000)． 幸运地是贝茜有一个很强大的武器，一次可以消除所有在一行或一列中的小行星，这种武器很贵，所以她希望尽量地少用．给出所有的小行星的位置，算出贝茜最少需要多少次射击就能消除所有的小行星． 第1行：两个整数N和K，用一个空格隔开． 第2行至K+1行：每一行有两个空格隔开的整数R,C(1≤R,C≤N)，分别表示小行星所在的行和列． 一个整数表示贝茜需要的最少射击次数，可以消除所有的小行星 3411132232样例输出2分析因为我们一次可以消除一行的小行星，我们就可以把小行星的行与列之间建一条边 这样，我们每消除一个点，就相当于把一行或者一列的小行星消除完 最后跑一个匈牙利就可以了 #include 给出一张由方块组成的地图。方块有许多种：墙，草，和空地。老板想让Robert在地图上放置尽可能多的机器人。每个机器人拿着一把激光枪，它可以同时向东西南北四个方向射击。机器人必须一直呆在它开始时被放在的位置并且不断地射击。激光束当然可以经过空地或草地，但不能穿过墙。机器人只能被放在空地上。 当然老板不希望看到机器人相互攻击。换句话说，两个机器人不能被放在一条线上（竖直或水平），除非它们中间有一堵墙。 由于你是一位机智的程序员和Robert的好基友之一，他请你帮他解决这个问题。也就是说，给出地图的描述，计算地图上最多能放置的机器人数量。 输入文件的第一行有两个正整数m,n（1<=m,n<=50），即地图的行数和列数。 接下来有m行，每行n个字符，这些字符是#,*或o，它们分别代表墙，草和空地。 输出一行一个正整数，即地图中最多放置的机器人数目 sample1:44o****###oo#o***osample2:44#oooo#oooo#o***#样例输出sample1:3sample2:5提示分析思路同上，不同的是我们要先把横向联通的模块处理出来，再把纵向联通的模块的处理出来，如果两个模块有交点，就把这两个模块连边，最后再用一个匈牙利算法求一下最大匹配 最后大家要注意一下输出，不要把sample\(XX\)也输出了 题目概述： 给你一个有向无环图，有n个点，m条有向边。 一个机器人可以从任意点开始沿着边的方向走下去。对于每一个机器人：走过的点不能再走过。 问你最少用几个机器人可以走完所有的n个点，不同的机器人可以走相同的点。 Theinputwillconsistofseveraltestcases.Foreachtestcase,twointegersN(1<=N<=500)andM(0<=M<=5000)aregiveninthefirstline,indicatingthenumberofpointsandthenumberofone-wayroadsinthegraphrespectively.EachofthefollowingMlinescontainstwodifferentintegersAandB,indicatingthereisaone-wayfromAtoB(0 Foreachtestoftheinput,printalinecontainingtheleastrobotsneeded. 1021122000样例输出112分析先补充一下二分图的几个扩展定理 这道题要用到的定理就是定理三 求最大匹配数的话，我们可以用Floyd，也可以用bitset 大致思路就是A到B有一条边，B到C有一条边，那么A也可以到C 用bitset的话不到50ms就可以过，用Floyd则要800ms Floyd版 #include #include jzyz每年的文理分班的时候，每个班都会有一些同学分到其他班，还会进入一些其他班的同学进入这个班。 小x负责安排座位，为了照顾分班带来的那种伤感情绪，小x制定了很人性化的座位安排计划，具体计划如下： 比如A和B都是本班学生且是好朋友，A分到了其他班，而C则是外班进入这个班的，C和A并不熟悉，而C和B关系很好，那么小x为了照顾A和C的情绪，就会让B坐在A的位置，C坐在B的位置。 当然，实际情况可能很复杂，比如一个班里的同学之间关系不一定好，外班进来的可能和本班很多人关系都很好。 现在告诉你，和小x所在班有关系的人一共有n个人，小x想知道有没有一个合理的方案来满足自己的座位安排计划。 本题为多组数据，第一行一个整数M，表示有M组测试数据。 对于每组测试数据，每组的第一行一个整数n，表示一共有n个人和这个班有关系。 接下来一行n个整数，第i个整数表示第i个人是否是本班学生（0表示不是，那么这次一定会分到本班，1表示是，分到其他班的也算是本班学生） 接下来一行n个整数，第i个整数表示第i个人是否要分到其他班（0表示留在本班，1表示分到其他班，如果第i个人不是本班的，那么他这次一定会被分来，那么第i个整数就是一个随机整数，没有实际意义） 接下来是一个n行n列的一个二维矩阵，第i行第j列的数表示第i个人和第j个人是否关系很好（1表示认识，0表示不认识），对角线上是0，但是自己肯定认识自己。 每组数据，如果存在一个方案，输出“_”(不含引号)。 如果没有方案，输出“T_T”(不含引号)。都是半角字符。 13110010011100100样例输出^_^数据范围与提示对于30%的数据满足1≤n≤12。对于100%的数据满足1≤n≤50,1≤T≤20。 大体思路就是把座位看成一堆点，把人看成另一堆点 如果某个人可以坐某个座位，那么把这一个人和这个座位连边 注意自己也可以和自己的座位连边 第1行3个正整数n,m,k，分别表示猫、狗和观众的数量 第2~k+1行，每行描述了一个观众的投票内容。 首先输入一个字符C或D紧接着是一个数字，表示某个观众想看到的动物，然后是一个空格隔开，接下去又是一个C或D加上一个数字，表示这个观众不想看到的动物，同一行中一定不会出现两个C或两个D。 输出一行一个正整数，表示小k在最优的安排下可以吸引多少观众来看表演。 124C1D1C1D1C1D2D2C1样例输出3数据范围与提示对于25%的数据n,m≤10,k≤25;对于100%的数据，n,m≤300,k≤500.