洛谷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 ...
51Nod 2006 飞行员配对（二分图最大匹配）
链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=2006思路：二分匹配 注意n m的关系代码： #include <iostream> #include <string.h> using nam...
二部图(二分图判定--dfs)
题目链接：二部图二部图时间限制：1000 ms | 内存限制：65535 KB 难度：1描述二 部图又叫二分图，我们不是求它的二分图最大匹配，也不是完美匹配，也不是多重匹配，而是证明一个图是不是二部图。证明二部图可以用着色来解决，即我们可以 用两种颜色去涂一个图，使的任意相连的两个顶点颜色不相同...
Girls and Boys HDU - 1068 二分图匹配（匈牙利）+最大独立集证明
最大独立集证明参考：https://blog.csdn.net/qq_34564984/article/details/52778763最大独立集证明：上图，我们用两个红色的点覆盖了所有边。我们证明的前提条件是已经达到最小覆盖。即条件1.已经覆盖所有边，条件2.所用的点数最小首先我们来证明蓝色点组成...
[kuangbin带你飞]专题十 匹配问题 二分图最大权匹配
二分图最大权匹配有km算法和网络流算法km算法模板默认解决最大权匹配的问题 而使用最小费用最大流 是解决最小权匹配问题这两种办法都可以求最大最小权 需要两次取反TAT 感觉讲km会很难的样子...P hdu2255km的模板题#include<stdio.h>#include<st...
bzoj3168 钙铁锌硒维生素 (矩阵求逆+二分图最小字典序匹配)
设第一套为A，第二套为B先对于每个B[i]判断他能否替代A[j]，即B[i]与其他的A线性无关设$B[i]=\sum\limits_{k}{c[k]*A[k]}$，那么只要看c[j]是否等于零即可，如果c[j]=0，就意味着可以用A[j]以外的线性表达出B[i]，所以不能B[i]替换A[j]，否则可...
hdu 2444(二分图) The Accomodation of Students
http://acm.hdu.edu.cn/showproblem.php?pid=2444大意是给定n个学生，他们之间可能互相认识，首先判断能不能将这些学生分为两组，使组内学生不认识；现想将学生两两分组，且保证每一组的学生都认识，这样分组可达到的最大组数为多大？判断二分图,然后求匈牙利算法求最大匹...