Yuki_fx

分类

未归档(69)

/ 注册

全部文章（共7篇）

HDU3718ZOJ3425 Similarity（The 2010 ACM-ICPC Asia Chengdu Regional Contest，加权二分图的最优匹配）

简单说就是求出两个字符串的相似程度。题目意思说的是学生得到一个任务，把不同物品分类，比如苹果，香蕉属于水果等，为了方便，给每个类别用字母编号。就得到题目中的字符串。每个学生的分类标准不一样，所以有不用的答案。现在问有多少个是正确的。最后结果是正确的答案除以总数。比如第一个样例，ABC 和...

图论二分图

2017-08-09

0 388

HDU 1528&&ZOJ 2223 Card Game Cheater（二分图匹配）

Card Game Cheater________________________________________Time Limit: 10 Seconds Memory Limit: 32768 KB________________________________________ Ad...

图论二分图

2017-09-04

0 536

POJ 1325 Machine Schedule(二分图匹配)

题目大意：有两个机器A和B，A机器有n个模式，B机器有m个模式,两个机器最初在0模式然后有k个作业，每个作业有三个参数i，a，b i代表作业编号，a和b代表第i作业要么在A机器的a模式下完成【或者】在B机器的b模式下完成问两个机器总共最少变换多少次可以完成所有作业解题思路：很水的一个二...

图论二分图

2017-08-10

0 380

南阳理工1015 （染色法判断二分图）

二部图时间限制：1000 ms | 内存限制：65535 KB 难度：1 描述二部图又叫二分图，我们不是求它的二分图最大匹配，也不是完美匹配，也不是多重匹配，而是证明一个图是不是二部图。证明二部图可以用着色来解决，即我们可以用两种颜色去涂一个图，使的任意相连的两个顶点颜色不相同，切任...

图论二分图

2017-08-31

0 442

HDU 2119 Matrix(二分图最小顶点覆盖)

Matrix Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Problem Description Give you a matrix(only contains 0 ...

图论二分图

2017-09-04

0 587

POJ -1422Air Raid

题目意思说，伞兵空降城镇，空降以后会选择一条路访问两个城镇。现在问要访问所有的城镇最少要空降多少次。看到题目就有点像最小边覆盖，用最小的边去覆盖所有的顶点。那么我们可以用二分图来求。最小边覆盖+最大匹配=V（顶点的个数）我们只需要构造一个二分图求得最大匹配以后用顶点个...

图论二分图

2017-08-23

0 360

UVA 11419 SAM I AM (最小点覆盖)

二分图匹配的题目，属于二分图的顶点覆盖问题。题目有点像之前做过的一道星际陨石的题目。题目大概的意思是说，给你一个地图，图上有些点上有东西。现在我有几门大炮，可以放在某一行或者某一列，然后这一行这一列的东西就会被打掉。现在要求开炮的次数最小，然后输出开炮方案。如果这道题目只叫你...

二分图

2017-10-14

0 735