二分匹配

题意：~ 思路： #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<int, int> PI; const int MAXN = 10010; const int MAXM = 10010; struct...

题意：~ 思路：最小权匹配，跑两遍KM，第二次建边要处理每个工人第一次做工的时间差。 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; typedef pair<int, int>...

题目链接：点我~~ 题意：给定n个学生，跟他们的排名范围，求最大说真话的人数，并输出字典序最大的编号。 思路：将学生作为X集，排名作为Y集，建立二分图，反向求出最大匹配，并标记其中被选择的学生。 #include <bits/stdc++.h> using namespace std; typedef long long LL; typed...

题目链接：点我~~ 题意：给n个字符串，然后对于任意两个字符串进行匹配，第一个翻转后与第二个匹配，最长公共前缀为得分，自己到自己为0。 思路：将字符串预处理建图，然后跑KM。 #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigne...

1.一个二分图中的最大匹配数等于这个图中的最小点覆盖数 König 定理是一个二分图中很重要的定理，它的意思是，一个二分图中的最大匹配数等于这个图中的最小 点覆盖数。如果你还不知道什么是最小点覆盖，我也在这里说一下：假如选了一个点就相当于覆盖了以它 为端点的所有边，你需要选择最少的点来覆盖所有的边。 2.最小路径覆盖＝｜G｜－最大匹配数   在一个 N*...