【标签：二分图】 - 第1页

1 二分图的匈牙利和KM算法感受

2015年11月24 - ： 二分图匹配（√），树形DP，分治算法，LCA，线段树。应该说实现这个任务很难，但是谁又能知道未来三天会发生什么呢？加油。写于2015.11.24 20：21 $(function () { $('pre.prettyprint

2 fzu2141（二分图着色）

2016年07月03 - 题意：给你一个图，现在让你找出一个边数不小于m/2的二分图，然后分别输出二分图的两部分。思路：很明显的二分图着色，只不过要有个优先着色的策略，尽量让二分图的点最多。 #include<stdio.h> #include<algorithm> #include<

3 [图的搜索]二分图判定

2015年08月10 - 二分图判定：给定一个具有n个顶点,v条边的图。要给图上每个顶点染色，并且要使相邻的顶点颜色不同。问是否能最多用2种颜色进行染色？题目保证没有重边和自环。限制条件： 1≤n≤1000 1≤v≤100000 样例输入

4 HDU 2444 The Accomodation of Students 判断是否为二分图，二分图的最大匹配

2013年12月27 - 题意：问给出的图是不是二分图，如果是输出最大匹配，不是输出"No"。可以利用BFS对图染色来判断一个图是否为二分图。首先图上各节点为无色的，任选一个未染色节点将其染上红色，然后以该点为原点进行BFS。从队列中取出点P，若P为红色，则将与其直接相连的点染上蓝色，否则染上

5 POJ 1466 Girls and Boys(二分图最大独立集)

2014年08月17 - POJ 1466 Girls and Boys(二分图最大独立集) http://poj.org/problem?id=1466 题意: 在一群男女同学之间存在”浪漫关系”,且该关系只存在于男同学与女同学之间.现在给出你比如2号学生与4号学生有浪漫关系(但是没给

6 【图-二分图染色】NOIP提高组2008双栈排序

2016年04月22 - 【问题描述】Tom最近在研究一个有趣的排序问题。如图所示，通过2个栈S1和S2，Tom希望借助以下4种操作实现将输入序列升序排序。操作a 如果输入序列不为空，将第一个元素压入栈S1 操作b 如果栈S1不为空，将S1栈顶元素弹出至输出序列操作c 如果输入序列不为空，将第一个元素压入栈S2 操作d 如

7 UVALive 4849 String Phone（2-sat、01染色）

2014年11月04 - 题目一眼看去以为是4-sat。。。题意：给n（n<=3000）个黑方块的坐标，保证黑方块没有公共边。对于每个黑方块选一个角作为结点，使得所选结点满足输入的一个无向图。其中距离为曼哈顿距离。输出是否有解。possible或impossible。对于每个黑方块，4个角落必须选且

8 二分图判定--黑白染色

2015年07月26 - 首先，二分图又叫二部图，特点是所有点分成两半，每一半内的点之间没有边相连，只有两半之间会有边相连，图内无奇环，当然，单点图或者有单点的图也属于二分图，因此最主要的区分就是图内无奇环了。对于一个图，是否是二分图，常用的方法是黑白染色，由于给定图常常不完全连通，所以只要对于每一个还未标记过的点

9 [BZOJ]2437 [NOI2011] 兔兔与蛋蛋 二分图博弈

2017年09月22 - Source Day2 [ Submit][ Status][ Discuss] HOME Back 比BZOJ1443简单的二分图博弈...格子的移动其实就是一次白一次黑，说白了就是在黑白格子上移动. 黑白染色后，同样的，非必需点后手必胜

10 ZOJ 1654 Place the Robots【二分图匹配】

2016年03月27 - 不得出现多个机器人，除非他们之间有墙相隔，现在问你最多能放几个器械人。这题比赛时学长说是二分图匹配，二分图匹配我会，可这题跟二分图啥关系？纠结到了结束都没想出来。后来问了下思路，顿觉智商受到了碾压。把空地分别按行和列编号，以行为例，每一行不能同时放机器人的空地标为同一个号，列同理。这样一来就把图分为

分类标签

2863 全部 511 二分图匹配 168 覆盖 110 code 72 判断 401 poj 628 算法 180 zoj 537 HDU 350 匈牙利算法 70 游戏 157 网络流 69 algorithm 85 uva 128 网络 91 路径 183 ACM 276 BZOJ 2158 二分 164 模板 2863 二分图 281 图论 165 问题 72 BLE 60 二分图最大匹配 1597 匹配