16
2017-07
2017-07
UVALive 7427 Elementary Math (二分匹配)
题意：~
思路：
#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...
07月16日
3,150
17
2017-02
2017-02
UVALive 6129 Sofa, So Good (KM)
题意：~
思路：最小权匹配，跑两遍KM，第二次建边要处理每个工人第一次做工的时间差。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int>...
02月17日
2,692
28
2016-09
2016-09
HDU 3729 I’m Telling the Truth (二分匹配)
题目链接：点我~~
题意：给定n个学生，跟他们的排名范围，求最大说真话的人数，并输出字典序最大的编号。
思路：将学生作为X集，排名作为Y集，建立二分图，反向求出最大匹配，并标记其中被选择的学生。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typed...
09月28日
2,095
28
2016-09
2016-09
HDU 3722 Card Game (KM)
题目链接：点我~~
题意：给n个字符串，然后对于任意两个字符串进行匹配，第一个翻转后与第二个匹配，最长公共前缀为得分，自己到自己为0。
思路：将字符串预处理建图，然后跑KM。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigne...
09月28日
2,336
13
2016-05
2016-05
HDU 1151 Air Raid (最小路径覆盖)
1.一个二分图中的最大匹配数等于这个图中的最小点覆盖数
König 定理是一个二分图中很重要的定理，它的意思是，一个二分图中的最大匹配数等于这个图中的最小 点覆盖数。如果你还不知道什么是最小点覆盖，我也在这里说一下：假如选了一个点就相当于覆盖了以它 为端点的所有边，你需要选择最少的点来覆盖所有的边。
2.最小路径覆盖＝｜G｜－最大匹配数
在一个 N*...
05月13日
2,557