POJ3057 Evacuation（二分图最大匹配）
人作X部；把门按时间拆点，作Y部；如果某人能在某个时间到达某门则连边。就是个二分图最大匹配。时间可以二分枚举，或者直接从1枚举时间然后加新边在原来的基础上进行增广。谨记：时间是个不可忽视的维度。 #include<cstdio> #include<cstring> #incl...
二分图最大匹配|UOJ#78|匈牙利算法|边表|Elena
#78. 二分图最大匹配从前一个和谐的班级，有 nlnl 个是男生，有 nrnr 个是女生。编号分别为 1,…,nl1,…,nl 和 1,…,nr1,…,nr。有若干个这样的条件：第 vv 个男生和第 uu 个女生愿意结为配偶。请问这个班级里最多产生多少对配偶？输入格式第一行三个正整数，nl,nr,...
【CF387D】George and Interesting Graph（二分图最大匹配）
题意：给定一张n点m边没有重边的有向图，定义一个有趣图为：存在一个中心点满足以下性质：1、除了这个中心点之外其他的点都要满足存在两个出度和两个入度。2、中心 u 需要对任意顶点 v（包括自己）有一条(u,v)的边和(v,u)的边，即他们都要互通。现在可以删除和添加边，使得给出的原图满足以上情况。询问...
UVALive 5903 Piece it together（二分图匹配）
给你一个n*m的矩阵，每个点为'B'或'W'或'.'。然后你有一种碎片。碎片可以旋转，问可否用这种碎片精确覆盖矩阵。N,M<=500WB 《==碎片W题目一看，感觉是精确覆盖（最近被覆盖洗脑了），但是仔细分析可以知道，DLX精确覆盖不是正解。因为N*M=250,000远超出DLX的可行规模（...
HDU 1068 Girls and Boys（模板——二分图最大匹配）
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1068Problem Descriptionthe second year of the university somebody started a study on the romantic relat...
洛谷P2055 [ZJOI2009]假期的宿舍 [二分图最大匹配]
题目描述学校放假了 · · · · · · 有些同学回家了，而有些同学则有以前的好朋友来探访，那么住宿就是一个问题。比如 A 和 B 都是学校的学生，A 要回家，而 C 来看B，C 与 A 不认识。我们假设每个人只能睡和自己直接认识的人的床。那么一个解决方案就是 B 睡 A 的床而 C 睡 B 的床...
UVA - 10004 Bicoloring（判断二分图——交叉染色法 / 带权并查集）
d.给定一个图，判断是不是二分图。s.可以交叉染色，就是二分图；否则，不是。另外，此题中的图是强连通图，即任意两点可达，从而dfs方法从一个点出发就能遍历整个图了。如果不能保证从一个点出发可以遍历整个图，那么编程要注意了，应该从每个点出发遍历一次。s2.带权并查集来判断，略复杂。先略过。先上个博客：...
HDU 3081：Marriage Match II（二分图匹配+并查集）
http://acm.hdu.edu.cn/showproblem.php?pid=3081题意：有n个男生n个女生，他们只有没有争吵或者女生a与男生A没有争吵，且女生b与女生a是朋友，因此女生b也可以和男生A过家家（具有传递性）。给出m个关系，代表女生a和男生b没有争吵过。给出k个关系，代表女生a...
HDU1045(KB10-A 二分图最大匹配)
Fire NetTime Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 12575 Accepted Submission(s): 7614P...
bzoj 2095: [Poi2010]Bridges（二分法+混合图的欧拉回路）
【题意】给定n点m边的无向图，对于边u,v，从u到v边权为c，从v到u的边权为d，问能够经过每条边一次且仅一次，且最大权值最小的欧拉回路。【思路】二分答案mid，然后切断权值大于mid的边，原图就变成了一个既有无向边又有有向边的混合图，则问题转化为求混合图上是否存在一个欧拉回路。无向图存在欧拉回路，...
HDU 1045 - Fire Net - [DFS][二分图最大匹配][匈牙利算法模板][最大流求二分图最大匹配]
题目链接：http://acm.split.hdu.edu.cn/showproblem.php?pid=1045Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)Problem Descr...
UVA 1349（二分图匹配）
1349 - Optimal Bus Route DesignTime limit: 3.000 secondsA big city wants to improve its bus transportation system. One of the improvement is to add sc...
LOJ 2548 「JSOI2018」绝地反击 ——二分图匹配+网络流手动退流
题目：https://loj.ac/problem/2548如果知道正多边形的顶点，就是二分答案、二分图匹配。于是写了个暴力枚举多边形顶点的，还很愚蠢地把第一个顶点枚举到 2*pi ，其实只要 \( \frac{2*pi}{n} \) 就行了。总之能得10分。#include<cstdio&g...
hdu 2444 二分图判断与最大匹配
题意：有n个学生，有m对人是认识的，每一对认识的人能分到一间房，问能否把n个学生分成两部分，每部分内的学生互不认识，而两部分之间的学生认识。如果可以分成两部分，就算出房间最多需要多少间，否则就输出No。首先判断是否为二分图，然后判断最大匹配Sample Input4 41 21 31 42 36 5...
[NOI2012]美食节——费用流（带权二分图匹配）+动态加边
题目描述小M发现，美食节共有n种不同的菜品。每次点餐，每个同学可以选择其中的一个菜品。总共有m个厨师来制作这些菜品。当所有的同学点餐结束后，菜品的制作任务就会分配给每个厨师。然后每个厨师就会同时开始做菜。厨师们会按照要求的顺序进行制作，并且每次只能制作一人份。此外，小M还发现了另一件有意思的事情: ...
HDU 5313 Bipartite Graph （二分图着色，dp）
题意：Soda有一个n个点m条边的二分图, 他想要通过加边使得这张图变成一个边数最多的完全二分图. 于是他想要知道他最多能够新加多少条边. 注意重边是不允许的.思路：先将二分图着色，将每个连通分量区分出左右两边的点，在着色过程中，顺便将每个连通分量两边的点数存起来，注意一个连通分量左右两边的点数是绑...
HDU 2255 奔小康赚大钱（带权二分图最大匹配）
HDU 2255 奔小康赚大钱（带权二分图最大匹配）Description传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素）...
POJ2195 Going Home[费用流|二分图最大权匹配]
Going HomeTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 22088 Accepted: 11155DescriptionOn a grid map there are n little men and n houses....
CodeForces - 688C：NP-Hard Problem （二分图&带权并查集）
Recently, Pari and Arya did some research about NP-Hard problems and they found the minimum vertex cover problem very interesting.Suppose the graph G ...
[kuangbin带你飞]专题十 匹配问题 二分图最大权匹配
二分图最大权匹配有km算法和网络流算法km算法模板默认解决最大权匹配的问题 而使用最小费用最大流 是解决最小权匹配问题这两种办法都可以求最大最小权 需要两次取反TAT 感觉讲km会很难的样子...P hdu2255km的模板题#include<stdio.h>#include<st...