二分图及一般图的匹配
二分图及一般图的匹配
二分图的判定
一般来说，如果题意说明了此题的图是由两个集合（每个集合内的点不会有边）则可直接判定为二分图，否则需要判定。判定方法为染色，对图上每个点进行交叉染色（黑-白-黑-白…），如果两个点之间存在边，且两点的颜色相同则不是二分图，由此可以得出如果一个图中出现奇数环，那么此图一定不是二分图。
为什么要进行二分图的判定？
原因是二分图的匹配算法不适用于带奇环的图的匹配，这种图需要另一种算法来解决。
增广路 如果不清楚什么是增广路的，在理解匹配之前可能需要先了解一下增广路，度娘讲得超级清楚
二分图问题
二分图的问题主要分为：最大匹配、最小点覆盖、最少边覆盖、最大独立集、多重匹配、最大权匹配，除此之外还有DAG的二分图问题，主要包括最少不相交覆盖路径问题和最少可相交覆盖问题，先了解一下几种问题的转换。
1、最小点覆盖=最大匹配数
2、最少边覆盖=点数-最大匹配数
3、最大独立集=点数-最大匹配数
最大匹配问题 二分图的最大匹配问题是二分图中比较基础但是非常重要的问题，二分图的其他问题基本都是在最大匹配的基础上做些改动。最大匹配其实就是将集合里的点进行配对（有边的点才能进行配对），被配对后，一个点只能出现在一个组合中。以下是最大匹配的几个例题（AC代码在文章末尾）
HDU 1045 Fire Net
题意：给定一张n*n的图，每行每列在没有阻挡的情况下只能放置一个棋子。
思路：重新构图，先将每行分解，再将每列分解，利用阻隔的墙进行分解，比如.X…可以分解为两行。然后进行最大匹配，新图的每行每列只能放置一个棋子，才能避免棋子之间的互相攻击。
HDU 1083 Courses
题意：N个学生，P门课，每个学生选择自己想要当课代表的课，问是否每门课都能有一个课代表，且课代表不能身兼数职，只能做一门课的课代表。
思路：学生Si选择课程Cj的话，则从Si向Cj连一条单向边，然后进行最大匹配，看看最大匹配数是否等于P。
HDU 2444 The Accomodation of Students
题意：给定n个人，m对关系，每对关系表示两人互相认识，但是A和B认识，B和C认识不代表A和C认识，问是否能将这n个人分为两个集合，每个集合中的人互相不认识，若不能输出NO，若能则为这n个人分配房间，每两个人一个房间，且同一个房间的人互相认识。
思路：此题其实是两个问题。问题一是能否将这n个人分为两个集合，且集合内的两个人互不相识，其实就是集合内的两点都是独立的，集合内的任意两点间不存在边，由此可以联想到二分图的性质，同一列的两点之间不存在边，因此这个问题可以用二分图的判定来解决。问题二是将n个人两两配对，且配对的两个人必须互相认识，问最大匹配数，第二个问题就是基础的最大匹配问题啦。
HDU 1281 棋盘游戏
题意：给定一个棋盘，棋盘中有些点可以放象棋，但是同行同列的象棋可以互相攻击，为了阻止互相攻击，每行每列可以放置象棋的格子中只能放一个象棋，除此之外还问了该棋盘中有多少个关键点，关键点就是如果此点不放置象棋，可能会导致最大放置数目减少。
思路：第一个问题很明显可以使用最大匹配来解决，对于第二个问题，我们采用枚举的方式来判定该点是否为关键点，遍历每个可放置象棋的格子g[i][j],将g[i][j]置为0，然后进行最大匹配，如果得到的匹配数小于最大匹配数则该点为关键点。
HDU 2819 Swap
题意：给定一个n*n的01矩阵，通过交换行或列使对角线都是1。若不能，输出-1，若能，输出交换次数，并且输出交换的行或者列。
思路：可以得出如果一行对应一列的1，有n个对应关系的话，是一定可以将对角线的格子变为1的，由此可以联想到二分图的最大匹配，另外，还需将交换的路径还原出来。
HDU 2389 Rain on your Parade
题意：在一个二维坐标系上有n个人和m把伞，每个人有自己的速度，问在时间t内，最多有多少人能拿到雨伞。
思路：如果人Pi在t的时间内能到达伞Uj，则由Pi向Uj连一条边，然后对图进行最大匹配就是答案，需要注意的一点是该题n和m比较大，复杂度较高，使用匈牙利的话会被踢飞，所以必须使用HK算法。
HDU 4185 Oil Skimming
题意：给定一块n * n的油田，每次能挖1 * 2或2 * 1矩形的油，每次挖的矩形里不能包含水。
思路：由于每次能挖12或21的矩形，由此可以联想到可以将油块两两配对，于是想到了二分图，将每个油块和周围挨着的油块相连，然后进行最大匹配，即得出答案
最小点覆盖（最少的点覆盖所有的边） HDU 1054 Strategic Game
题意：给定一棵树，选取树上最少的节点使得可以覆盖整棵树。
思路：由于题目给的是树，树可以按层分出两个集合，使得集合里的任意两点均不会有边，满足二分图的性质，故题目给定的是二分图，可以用二分图的最小点覆盖来解决
最小边覆盖（图中不含孤立点）（这部分内容出自大佬的博客） 二分图中最小边覆盖=顶点数-最小点覆盖（最大匹配）
最小边覆盖：实质是个边集，这个集合里的边能覆盖所有的点，最小边覆盖是满足这个要求的所有边集中边数最少的一个。这里顶点数等于总的顶点数，是二分图两边的顶点数，不是一边。
证明：设最大匹配数为m，总顶点数为n。为了使边数最少，又因为一条边最多能干掉两个点，所以尽量用边干掉两个点。也就是取有匹配的那些边，当然这些边是越多越好，那就是最大匹配了，所以先用最大匹配数目的边干掉大多数点。剩下的解决没有被匹配的点，就只能一条边干掉一个点了，设这些数目为a。显然，2m+a=n，而最小边覆盖=m+a，所以最小边覆盖=（2m+a）-m=n-m。
POJ 3020 Antenna Placement
题意：给定一个n * m的矩阵， * 表示城市，o表示空地，在这个矩阵上空建立基站，相邻的两个城市可以共用一个基站，问最少应该修建多少个基站？
思路：因为要覆盖所有的城市，所以可以想到最小边覆盖，最小边覆盖就是最小的边集使图中所有点都与这个边集中的某边有关。
最大独立集 最大独立集=n-最小点覆盖
因为最小点覆盖的定义是所有边的一个端点都在最小点覆盖集合里，且这个集合是最小的，故减去这些点，
剩下的就是相互独立的。
HDU 3829 Cat VS Dog
题意：动物园里有n只猫和m只狗，现在有p个小朋友去参观动物园，每个小朋友都有自己喜欢的一只猫或狗，还有自己讨厌的一只猫或狗，如果自己喜欢的动物不在或自己讨厌的动物在的话小朋友就会非常不开心，现在想选择将一些动物带走，使得开心的人数最多，问最多能使多少人开心。
思路：一开始一只考虑猫和狗的关系，想不出方案，然后去瞟了一眼网上的题解。正解是将小朋友作为点来构图，如果小朋友A喜欢的是小朋友B讨厌的动物，则将两个小朋友连起来，很明显，连起来的两个小朋友中只能有一人开心，于是做最大匹配，再用P-最大匹配数就是答案。
多重匹配 多重匹配就是一对多的配对，解决问题时可以选择网络流也可以选择在最大匹配算法的基础上稍微改动一下，具体看情况
POJ 2289 Jamie’s Contact Groups
题意：给定n个人，m个分组，给定每个人可能分到的分组，每个人只能出现在一个分组中，现在要让你去分组，并且使最大分组的size最小，最后输出最大分组的大小
思路：首先，看到使最大分组size最小，肯定想到二分答案，然后每个人只能出现一次，想到匹配，所以就是二分+多重匹配。
POJ 2112 Optimal Milking
题意给出c头牛，n个挤奶器，每个挤奶器最多接待m头牛，每头牛和挤奶器有自己的位置（以下内容将牛和挤奶器合称为实体），实体间都有一定的距离，题目给出所有实体间的距离矩阵，请问走的最远的牛的距离最小是多少？
思路：又是使最大的值最小，所以想到二分，然后一头牛只能去往一个挤奶器，每个挤奶器可以接待多头牛，于是想到多重匹配。
POJ 3189 Steady Cow Assignment
题意：给定n头牛,m个牛棚，每个牛棚有自己的容量，现在的牛牛们对自己所在的牛棚不是很满意，所以农夫决定重新安排，他将根据牛牛们心中对牛棚的排名来安排，现在想要使所有牛牛中去往牛棚最满意的排名和最不满意的排名之间的差距最小（可能是为了平衡牛牛们的心理？？？）
思路：这题一开始理解错了，我以为是使最差的最小，其实是使牛牛们的喜爱程度差距最小，又是使…最小，首先想到二分，然后再加个多重匹配就解决了。
最大权匹配 HDU 2255 奔小康赚大钱
题意：传说在遥远的地方有一个非常富裕的村落,有一天,村长决定进行制度改革：重新分配房子。
这可是一件大事,关系到人民的住房问题啊。村里共有n间房间,刚好有n家老百姓,考虑到每家都要有房住（如果有老百姓没房子住的话，容易引起不安定因素），每家必须分配到一间房子且只能得到一间房子。
另一方面,村长和另外的村领导希望得到最大的效益,这样村里的机构才会有钱.由于老百姓都比较富裕,他们都能对每一间房子在他们的经济范围内出一定的价格,比如有3间房子,一家老百姓可以对第一间出10万,对第2间出2万,对第3间出20万.(当然是在他们的经济范围内).现在这个问题就是村领导怎样分配房子才能使收入最大.(村民即使有钱购买一间房子但不一定能买到,要看村领导分配的).
思路：最大权匹配裸题，套个KM板子就行了
HDU 3488 Tour
题意：某人要去某个城市环游，要求每个景点不重样，给定了城市里一些景点的距离，路线中有些有向环，让你求出环游城市的最小距离。
思路：其实我并没有读懂题意，看了一下网上的题解，因为是有向环，所以所有可去的点的出入度都是1，所以想到拆点，然后进行最大权匹配，由于是使距离最小，所以每条边求下反。
DAG的二分图
最小不相交路径覆盖 最小不相交路径覆盖=最小边覆盖=n-最大匹配数
每条路径不能有相同的端点
HDU 1151 Air Raid
题意：给定n个地点，m个街道，每条街道都是单向的，现要向这个地方投放一些伞兵来巡察街道，要求伞兵之间不能碰面，伞兵可以沿着街道走到另一个地点去巡察，问最少需派多少个伞兵
思路：该题是求DAG图的不相交最小路径覆盖，可以在构图完后使用最大匹配算法，然后直接使用上述公式求出答案
最小可相交路径覆盖 每条路径可以有相同的端点
解决这类问题的方法就是先对图使用floyed进行传递闭包，然后剩下的就和最小不相交路径覆盖相同了。
POJ 2594 Treasure Exploration
题意：给定n个点，m条路，问至少放置多少个机器人，能将所有的点访问完。
思路：本题的机器人是可以碰面的（可以路过同一个点），于是先对图进行传递闭包，然后剩下的就和最小不相交路径覆盖求法一样了。
一般图的最大匹配
带奇环的图不能适用二分图的求法，只能另辟蹊径，选择带花树算法，想要了解什么是带花树可以移步到大佬的博客
URAL 1099 Work Scheduling
题意：有n个士兵和m个可配对的关系，每个士兵只能配对一次，问最大能有多少对，并输出谁和谁配对。
思路：由于可能存在奇环，所以选择带花树匹配算法
【二分图及一般图的匹配】HDU 4687 Boke and Tsukkomi
题意：给出n个人和m对关系，问有多少个关系是一定不能存在的（存在可能会使配对的组数更少），并按序号输出。
思路：先使用带花树算法求出最大匹配数cnt，然后枚举每对关系，假设这一对一定要配对，重新建图，将这两点从图中去掉，再用带花树算法求最大匹配数cur，如果cur
#include
using namespace std;
const int N = 50;
int g[N][N];
int cx[N], cy[N];
bool vis[N];
int n;
char s[5][5];
int belr[5][5];
int belc[5][5];
int cnum, rnum;
int line(int u) {
for (int i = 1;
i <= cnum;
i++) {
if (g[u][i] && !vis[i]) {
vis[i] = true;
if (cy[i] == -1 || line(cy[i])) {
cx[u] = i;
cy[i] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= rnum;
i++) {
if (cx[i] == -1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans;
}
int main() {
while (scanf("%d", &n)==1&&n) {
for (int i = 1;
i <= n;
i++)scanf("%s", s[i]+1);
int cnt = 0;
for (int i = 1;
i <= n;
i++) {
s[i][0] = '$';
for (int j = 1;
j <= n;
j++) {
if (s[i][j] == 'X')continue;
if (s[i][j - 1] == '.')belr[i][j] = belr[i][j - 1];
else belr[i][j] = ++cnt;
}
}
rnum = cnt;
cnt = 0;
for (int j = 1;
j <= n;
j++) {
s[0][j] = '$';
for (int i = 1;
i <= n;
i++) {
if (s[i][j] == 'X')continue;
if (s[i - 1][j] == '.')belc[i][j] = belc[i - 1][j];
else belc[i][j] = ++cnt;
}
}
cnum = cnt;
memset(g, 0, sizeof(g));
for (int i = 1;
i <= n;
i++)
for (int j = 1;
j <= n;
j++)
if (s[i][j] == '.')g[belr[i][j]][belc[i][j]] = 1;
printf("%d\n", maxmatch());
}
return 0;
}
HDU 2444 The Accomodation of Students
#include
using namespace std;
const int N = 205;
int n, m;
int c[N];
int match[N];
int head[N], tot;
bool vis[N];
bool flag;
struct Edge {
int to;
int nxt;
}e[N*N];
void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
void dfs(int u,int f) {
if (!flag)return;
c[u] = f;
for (int v,i = head[u];
i != -1;
i = e[i].nxt) {
v = e[i].to;
if (!c[v])dfs(v, -f);
else if (c[v] == c[u]) {
flag = false;
return;
}
}
}
bool judge() {
memset(c, 0, sizeof(c));
flag = true;
for (int i = 1;
i <= n;
i++) {
if (!c[i])dfs(i, 1);
if (!flag)break;
}
return flag;
}
int line(int u) {
for (int v,i = head[u];
i != -1;
i = e[i].nxt) {
v = e[i].to;
if (!vis[v]) {
vis[v] = true;
if (match[v] == -1 || line(match[v])) {
match[v] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
int ans = 0;
memset(match, -1, sizeof(match));
for (int i = 1;
i <= n;
i++) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
return ans;
}
int main() {
while (scanf("%d%d", &n, &m) != EOF) {
memset(head, -1, sizeof(head));
tot = 0;
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v);
add(v, u);
}
if (!judge())printf("No\n");
else printf("%d\n", maxmatch()/2);
}
return 0;
}
HDU 1083 Courses
#include
using namespace std;
const int N = 3e2 + 10;
int head[N], tot;
int cx[N], cy[N];
bool vis[N];
int p, n;
struct Edge {
int to;
int nxt;
}e[N*N];
void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
int line(int u) {
for (int v,i = head[u];
i != -1;
i = e[i].nxt) {
v = e[i].to;
if (!vis[v]) {
vis[v] = true;
if (cy[v] == -1 || line(cy[v])) {
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= p;
i++) {
if (cx[i]==-1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
memset(head, -1, sizeof(head));
tot = 0;
scanf("%d%d", &p, &n);
for (int k,i = 1;
i <= p;
i++) {
scanf("%d", &k);
while (k--) {
int to;
scanf("%d", &to);
add(i, to);
}
}
printf(maxmatch() == p ? "YES\n" : "NO\n");
}
return 0;
}
HDU 1281 棋盘游戏
#include
using namespace std;
const int N = 105;
int cx[N], cy[N];
int g[N][N];
int n, m, k;
bool vis[N];
int maxx;
int line(int u) {
for (int i = 1;
i <= m;
i++) {
if (!vis[i] && g[u][i]) {
vis[i] = true;
if (cy[i] == -1 || line(cy[i])) {
cx[u] = i;
cy[i] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= n;
i++) {
if (cx[i] == -1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans;
}
int main() {
int ex = 0;
while (scanf("%d%d%d", &n, &m, &k) ==3) {
memset(g, 0, sizeof(g));
while (k--) {
int x, y;
scanf("%d%d", &x, &y);
g[x][y] = 1;
}
maxx = maxmatch();
int ans = 0;
for (int i = 1;
i <= n;
i++) {
for (int j = 1;
j <= m;
j++) {
if (g[i][j]) {
g[i][j] = 0;
if (maxmatch() < maxx)ans++;
g[i][j] = 1;
}
}
}
printf("Board %d have %d important blanks for %d chessmen.\n", ++ex, ans,maxx);
}
return 0;
} HDU 2819 Swap
#include
using namespace std;
const int N = 105;
int g[N][N];
int n;
int cx[N], cy[N];
bool vis[N];
int tot;
int a[N], b[N];
int line(int u) {
for (int i = 1;
i <= n;
i++) {
if (g[u][i] && !vis[i]) {
vis[i] = true;
if (cy[i] == -1 || line(cy[i])) {
cx[u] = i;
cy[i] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= n;
i++) {
if (cx[i]==-1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans;
}
int main() {
while (scanf("%d", &n) == 1) {
for (int i = 1;
i <= n;
i++)
for (int j = 1;
j <= n;
j++)
scanf("%d", &g[i][j]);
if (maxmatch() < n)printf("-1\n");
else {
tot = 0;
for (int i = 1;
i <= n;
i++) {//cx[i]=j ,swap(cj,ci)
if (cx[i] != i) {
a[++tot] = i;
b[tot] = cx[i];
int j = cx[i];
int t = cy[i];
swap(cy[i], cy[j]);
swap(cx[i], cx[t]);
//swap()
}
}
printf("%d\n", tot);
for (int i = 1;
i <= tot;
i++)printf("C %d %d\n", a[i], b[i]);
}
}
return 0;
}
HDU 2389 Rain on your Parade
#include
#include
#include
#include
#include
using namespace std;
const int N = 3005;
const int INF = 0x3f3f3f3f;
int head[N], tot;
int n, m;
int cx[N], cy[N];
int dx[N], dy[N];
bool vis[N];
int tm;
int dis;
struct Edge {
int to;
int nxt;
}e[N*N];
struct Person {
double x, y;
double v;
}p[N];
void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
bool judge(Person p, int x, int y) {
double dis = sqrt((p.x - x)*(p.x - x) + (p.y - y)*(p.y - y));
if (dis / p.v > (tm + 0.0))return false;
return true;
}
bool bfs() {
dis = INF;
memset(dx, -1, sizeof(dx));
memset(dy, -1, sizeof(dy));
queueQ;
for (int i = 1;
i <= n;
i++) {
if (cx[i] == -1) {
Q.push(i);
dx[i] = 0;
}
}
while (!Q.empty()) {
int u = Q.front();
Q.pop();
if (dx[u] > dis)break;
for (int v,i = head[u];
i != -1;
i = e[i].nxt) {
v = e[i].to;
if (dy[v] == -1) {
dy[v] = dx[u] + 1;
if (cy[v] == -1)dis = dy[v];
else {
dx[cy[v]] = dy[v] + 1;
Q.push(cy[v]);
}
}
}
}
return dis != INF;
}
int findpath(int u) {
for (int v,i = head[u];
i != -1;
i = e[i].nxt) {
v = e[i].to;
if (!vis[v] && dy[v] == dx[u] + 1) {
vis[v] = 1;
if (cy[v] != -1 && dy[v] == dis)continue;
if (cy[v] == -1 || findpath(cy[v])) {
cy[v] = u;
cx[u] = v;
return 1;
}
}
}
return 0;
}
int maxmatch() {
int res = 0;
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
while (bfs()) {
memset(vis, 0, sizeof(vis));
for (int i = 1;
i <= n;
i++) {
if (cx[i] == -1)res += findpath(i);
}
}
return res;
}
int main() {
int t;
scanf("%d", &t);
int ex = 0;
while (t--) {
memset(head, -1, sizeof(head));
tot = 0;
scanf("%d%d", &tm, &n);
for (int i = 1;
i <= n;
i++)scanf("%lf%lf%lf", &p[i].x, &p[i].y, &p[i].v);
scanf("%d", &m);
for (int x,y,i = 1;
i <= m;
i++) {
scanf("%d%d", &x, &y);
for (int j = 1;
j <= n;
j++)
if (judge(p[j], x, y))add(j, i);
}
//if (ex)printf("\n");
printf("Scenario #%d:\n%d\n\n", ++ex,maxmatch());
}
return 0;
} HDU 4185 Oil Skimming
#include
using namespace std;
const int N = 605;
char s[N][N];
int bel[N][N];
int cnt;
int n;
int dir[4][2] = { -1,0,1,0,0,-1,0,1 };
int head[N*N];
int tot;
int cx[N*N], cy[N*N];
bool vis[N*N];
struct Edge {
int to;
int nxt;
}e[5*N*N];
void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
int line(int u) {
for (int v,i = head[u];
i != -1;
i = e[i].nxt) {
v = e[i].to;
if (!vis[v]) {
vis[v] = true;
if (cy[v]==-1 || line(cy[v])) {
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= cnt;
i++) {
if (cx[i]==-1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans / 2;
}
int main() {
int t;
scanf("%d", &t);
int ex = 0;
while (t--) {
scanf("%d", &n);
cnt = 0;
for (int i = 1;
i <= n;
i++) {
scanf("%s", s[i] + 1);
for (int j = 1;
j <= n;
j++) {
if (s[i][j] == '#')bel[i][j] = ++cnt;
}
}
memset(head, -1, sizeof(head));
tot = 0;
for (int i = 1;
i <= n;
i++) {
for (int j = 1;
j <= n;
j++) {
if (s[i][j] != '#')continue;
for (int k = 0;
k < 4;
k++) {
int x = dir[k][0] + i;
int y = dir[k][1] + j;
if (x >= 1 && x <= n&&y >= 1 && y <= n&&s[x][y] == '#')add(bel[i][j], bel[x][y]);
}
}
}
printf("Case %d: %d\n",++ex, maxmatch());
}
return 0;
} POJ 3020 Antenna Placement
#include
#include
#include
#include
using namespace std;
const int N = 50;
char s[N][N];
int bel[N][N];
int cnt;
int n, m;
int dir[4][2] = { -1,0,1,0,0,-1,0,1 };
int head[N*N];
int tot;
int cx[N*N], cy[N*N];
bool vis[N*N];
struct Edge {
int to;
int nxt;
}e[5*N*N];
void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
int line(int u) {
for (int v,i = head[u];
i != -1;
i = e[i].nxt) {
v = e[i].to;
if (!vis[v]) {
vis[v] = true;
if (cy[v]==-1 || line(cy[v])) {
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= cnt;
i++) {
if (cx[i]==-1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return cnt-ans / 2;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
cnt = 0;
for (int i = 1;
i <= n;
i++) {
scanf("%s", s[i] + 1);
for (int j = 1;
j <= m;
j++) {
if (s[i][j] == '*')bel[i][j] = ++cnt;
}
}
memset(head, -1, sizeof(head));
tot = 0;
for (int i = 1;
i <= n;
i++) {
for (int j = 1;
j <= m;
j++) {
if (s[i][j] != '*')continue;
for (int k = 0;
k < 4;
k++) {
int x = dir[k][0] + i;
int y = dir[k][1] + j;
if (x >= 1 && x <= n&&y >= 1 && y <= m&&s[x][y] == '*')add(bel[i][j], bel[x][y]);
}
}
}
printf("%d\n",maxmatch());
}
return 0;
} HDU 1054 Strategic Game
#include
using namespace std;
const int N = 15e2 + 10;
struct Edge {
int to;
int nxt;
}e[N*100];
int head[N], tot;
int n;
int cx[N], cy[N];
bool vis[N];
void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
int line(int u) {
for (int v,i = head[u];
i != -1;
i = e[i].nxt) {
v = e[i].to;
if (!vis[v]) {
vis[v] = true;
if (cy[v] == -1 || line(cy[v])) {
cy[v] = u;
cx[u] = v;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= n;
i++) {
if (cx[i] == -1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans/2;
}
int main() {
while (scanf("%d", &n) == 1) {
memset(head, -1, sizeof(head));
tot = 0;
for (int u,v,k,i = 1;
i <= n;
i++) {
scanf("%d:(%d)", &u, &k);
u++;
while (k--) {
scanf("%d", &v);
v++;
add(u, v);
add(v, u);
}
}
printf("%d\n", maxmatch());
}
return 0;
}
HDU 1151 Air Raid
#include
using namespace std;
const int N = 125;
int n, m;
int cx[N], cy[N];
int g[N][N];
bool vis[N];
int line(int u) {
for (int i = 1;
i <= n;
i++) {
if (g[u][i] && !vis[i]) {
vis[i] = true;
if (cy[i] == -1 || line(cy[i])) {
cx[u] = i;
cy[i] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= n;
i++) {
if (cx[i] == -1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans;
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &m);
memset(g, 0, sizeof(g));
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
g[u][v] = 1;
}
printf("%d\n", n - maxmatch());
}
return 0;
} POJ 2594 Treasure Exploration
#include
#include
#include
#include
using namespace std;
const int N = 505;
int n, m;
int cx[N], cy[N];
int g[N][N];
bool vis[N];
int line(int u) {
for (int i = 1;
i <= n;
i++) {
if (g[u][i] && !vis[i]) {
vis[i] = true;
if (cy[i] == -1 || line(cy[i])) {
cx[u] = i;
cy[i] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= n;
i++) {
if (cx[i] == -1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans;
}
void floyed() {
for (int i = 1;
i <= n;
i++) {
for (int j = 1;
j <= n;
j++) {
if (g[i][j])continue;
for (int k = 1;
k <= n;
k++) {
if (g[i][k] && g[k][j])g[i][j] = 1;
}
}
}
}
int main() {
while (scanf("%d%d", &n, &m)!=EOF&&n) {
memset(g, 0, sizeof(g));
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
g[u][v] = 1;
}
floyed();
printf("%d\n", n - maxmatch());
}
return 0;
}
HDU 3829 Cat VS Dog
#include
using namespace std;
const int N = 505;
int n, m,p;
int cx[N], cy[N];
bool vis[N];
vectorg[N];
struct Person {
char lc;
int lid;
char dc;
int did;
}pe[N];
bool judge(Person p1,Person p2) {
if (p1.lc == p2.dc&&p1.lid == p2.did)return true;
if (p2.lc == p1.dc&&p2.lid == p1.did)return true;
return false;
}
int line(int u) {
for (int v, i = 0;
i < g[u].size();
i++) {
v = g[u][i];
if (!vis[v]) {
vis[v] = true;
if (cy[v] == -1 || line(cy[v])) {
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
int ans = 0;
for (int i = 1;
i <= p;
i++) {
if (cx[i] == -1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans / 2;
}
int main() {
while (scanf("%d%d%d", &n, &m, &p) != EOF) {
for (int i = 1;
i <= p;
i++)g[i].clear();
for (int i = 1;
i <= p;
i++) {
getchar();
scanf("%c%d %c%d", &pe[i].lc, &pe[i].lid, &pe[i].dc, &pe[i].did);
}
for (int i = 1;
i <= p;
i++) {
for (int j = i + 1;
j <= p;
j++) {
if (judge(pe[i], pe[j])) {
g[i].push_back(j);
g[j].push_back(i);
}
}
}
printf("%d\n", p - maxmatch());
}
return 0;
}
POJ 2289 Jamie’s Contact Groups
//二分图多重匹配
#include
#include
#include
#include
#include
using namespace std;
const int N = 1e3 + 10;
int cx[N], cy[N][N];
int cnt[N];
bool vis[N];
vectorg[N];
int n, m;
int maxx;
char name[20];
int getnum(char s[]) {
int t = 0;
for (int i = 0;
s[i];
i++){
t *= 10;
t += (s[i] - '0');
}
return t;
}
int line(int u) {
for (int i = 0;
i < g[u].size();
i++) {
int v = g[u][i];
if (!vis[v]) {
vis[v] = true;
if (cnt[v] < maxx) {
cx[u] = v;
cy[v][++cnt[v]] = u;
return 1;
}
else {
for (int j = 1;
j <= maxx;
j++) {
if (line(cy[v][j])) {
cx[u] = v;
cy[v][j] = u;
return 1;
}
}
}
}
}
return 0;
}
bool maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cnt, 0, sizeof(cnt));
int ans = 0;
for (int i = 1;
i <= n;
i++) {
if (cx[i] == -1) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
}
return ans == n;
}
int main() {
while (scanf("%d%d", &n, &m)!=EOF && n) {
char ch;
for (int i = 1;
i <= n;
i++)g[i].clear();
for (int v,i = 1;
i <= n;
i++) {
scanf("%s", name);
while (scanf("%d", &v)) {
g[i].push_back(v);
ch = getchar();
if (ch == '\n')break;
}
}
int l = 0, r = n;
int ans;
while (l <= r) {
int mid = (l + r) / 2;
maxx = mid;
if (maxmatch()) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
printf("%d\n", ans);
}
}
POJ 2112 Optimal Milking
#include
#include
#include
#include
using namespace std;
const int N = 250;
const int M = 35;
const int INF = 0x3f3f3f3f;
int g[N][N];
int mp[N][N];
int cx[N], cy[M][M];
int cnt[M];
bool vis[M];
int k, c, m;
int maxx;
int line(int u) {
for (int i = 1;
i <= k;
i++) {
if (mp[u][i]>maxx)continue;
if (vis[i])continue;
vis[i] = 1;
if (cnt[i] < m) {
cx[u] = i;
cy[i][++cnt[i]] = u;
return 1;
}
else {
for (int j = 1;
j <= m;
j++) {
if (line(cy[i][j])) {
cx[u] = i;
cy[i][j] = u;
return 1;
}
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cnt, 0, sizeof(cnt));
int ans = 0;
for (int i = k + 1;
i <= k + c;
i++) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
return ans;
}
bool solve(int x) {
maxx = x;
memset(mp, INF, sizeof(mp));
for (int i = 1;
i <= k + c;
i++) {
for (int j = 1;
j <= k + c;
j++) {
if (g[i][j] > x||g[i][j]==0)continue;
mp[i][j] = g[i][j];
}
}
for (int u = 1;
u <= k + c;
u++) {
for (int i = 1;
i <= k + c;
i++)
{
if (mp[i][u] == INF)continue;
for (int j = 1;
j <= k + c;
j++) {
mp[i][j] = min(mp[i][j], mp[i][u] + mp[u][j]);
}
}
}
return maxmatch() == c;
}
int main() {
scanf("%d%d%d", &k, &c, &m);
for (int i = 1;
i <= k + c;
i++)
for (int j = 1;
j <= k + c;
j++)
scanf("%d", &g[i][j]);
int l = 0, r = 1e4;
int ans = r;
while (l <= r) {
int mid = (l + r) / 2;
if (solve(mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
} POJ 3189 Steady Cow Assignment
#include
#include
#include
#include
#include
using namespace std;
const int N = 1005;
const int M = 25;
vectorg[N];
bool vis[M];
int cnt[M];
int cap[M];
int cx[N], cy[M][N];
int n, m;
int l, r;
int line(int u) {
for (int v,i = l;
i < r;
i++) {
v = g[u][i];
if (vis[v])continue;
vis[v] = true;
if (cnt[v] < cap[v]) {
cx[u] = v;
cy[v][++cnt[v]] = u;
return 1;
}
else {
for (int j = 1;
j <= cnt[v];
j++) {
if (line(cy[v][j])) {
cx[u] = v;
cy[v][j] = u;
return 1;
}
}
}
}
return 0;
}
int maxmatch() {
memset(cx, -1, sizeof(cx));
memset(cnt, 0, sizeof(cnt));
int ans = 0;
for (int i = 1;
i <= n;
i++) {
memset(vis, 0, sizeof(vis));
ans += line(i);
}
return ans;
}
bool solve(int x) {
for (int i = 1;
i <= m - x + 1;
i++) {
l = i - 1;
r = i + x - 1;
if (maxmatch() == n)return 1;
}
return 0;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1;
i <= n;
i++) {
for (int v,j = 1;
j <= m;
j++) {
scanf("%d", &v);
g[i].push_back(v);
}
}
for (int i = 1;
i <= m;
i++)scanf("%d", &cap[i]);
int l = 1, r = m;
int ans = m;
while (l <= r) {
int mid = (l + r) / 2;
if (solve(mid)) {
ans = mid;
r = mid - 1;
}
else l = mid + 1;
}
printf("%d\n", ans);
return 0;
} HDU 2255 奔小康赚大钱
#include
using namespace std;
const int N = 305;
const int INF = 0x3f3f3f3f;
int wx[N], wy[N];
int cx[N], cy[N];
int visx[N], visy[N];
int cntx, cnty;
int mp[N][N];
int slack[N];
bool dfs(int u) {
visx[u] = 1;
for (int v = 1;
v <= cnty;
v++) {
if (!visy[v] && mp[u][v] != INF) {
int t = wx[u] + wy[v] - mp[u][v];
if (t == 0) {
visy[v] = 1;
if (cy[v] == -1 || dfs(cy[v])) {
cx[u] = v;
cy[v] = u;
return 1;
}
}
else if (t > 0) {
slack[v] = min(slack[v], t);
}
}
}
return false;
}
int KM() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
memset(wx, 0, sizeof(wx));
memset(wy, 0, sizeof(wy));
for (int i = 1;
i <= cntx;
i++) {
for (int j = 1;
j <= cnty;
j++) {
if (mp[i][j] == INF)continue;
wx[i] = max(wx[i], mp[i][j]);
}
}
for (int i = 1;
i <= cntx;
i++) {
memset(slack, INF, sizeof(slack));
while (1) {
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if (dfs(i))break;
int minz = INF;
for (int j = 1;
j <= cnty;
j++)
if (!visy[j] && minz > slack[j])
minz = slack[j];
for (int j = 1;
j <= cntx;
j++)
if (visx[j])wx[j] -= minz;
for (int j = 1;
j <= cnty;
j++)
if (visy[j])wy[j] += minz;
else slack[j] -= minz;
}
}
int ans = 0;
for (int i = 1;
i <= cntx;
i++)
if (cx[i] != -1)ans += mp[i][cx[i]];
return ans;
}
int n;
int main() {
while (scanf("%d", &n) != EOF) {
cntx = cnty = n;
for (int i = 1;
i <= n;
i++)
for (int j = 1;
j <= n;
j++)
scanf("%d", &mp[i][j]);
printf("%d\n", KM());
}
return 0;
}
HDU 3488 Tour
#include
using namespace std;
typedef long long ll;
const int maxn = 210;
const int INF = 0x3f3f3f3f;
int wx[maxn], wy[maxn];
int cx[maxn], cy[maxn];
int visx[maxn], visy[maxn];
int cntx, cnty;
int g[maxn][maxn];
int minz;
bool dfs(int u) {
visx[u] = 1;
for (int v = 1;
v <= cnty;
v++) {
if (!visy[v] && g[u][v] != -INF) {
int t = wx[u] + wy[v] - g[u][v];
if (t == 0) {
visy[v] = 1;
//加入增广路
if (cy[v] == -1 || dfs(cy[v])) {
cx[u] = v;
cy[v] = u;
return 1;
}
}
else if (t > 0)
minz = min(minz, t);
}
}
return 0;
}
int KM() {
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
memset(wx, 0, sizeof(wx));
memset(wy, 0, sizeof(wy));
for (int i = 1;
i <= cntx;
i++) {
for (int j = 1;
j <= cnty;
j++) {
if (g[i][j] == -INF)continue;
wx[i] = max(wx[i], g[i][j]);
}
}
for (int i = 1;
i <= cntx;
i++) {
while (1) {
minz = INF;
memset(visx, 0, sizeof(visx));
memset(visy, 0, sizeof(visy));
if (dfs(i))break;
for (int j = 1;
j <= cntx;
j++)
if (visx[j])wx[j] -= minz;
for (int j = 1;
j <= cnty;
j++)
if (visy[j])wy[j] += minz;
}
}
int ans = 0;
for (int i = 1;
i <= cntx;
i++)
if (cx[i] != -1)ans += g[i][cx[i]];
return ans;
}
int n, m;
int main() {
int t;
scanf("%d", &t);
while (t--) {
memset(g, -INF, sizeof(g));
scanf("%d%d", &n, &m);
cntx = cnty = n;
while (m--) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
g[u][v] = max(g[u][v], -w);
}
printf("%d\n", -KM());
}
return 0;
}
URAL 1099 Work Scheduling
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
const int N = 250;
const int M = 4 * N*N;
struct Edge {
int to;
int nxt;
}e[M];
int head[N], tot;
int vis[N],match[N], f[N], pre[N], Id, id[N];
//vis[i]: 0--未染色，1--黑色，2--白色
//match[i]: i的匹配点
//f[i]: i再带花树中的祖先
//pre[i]: i的非匹配边的另一点
//id: 找LCA用
int n, m, ans, u, v;
queueq;
void Init() {
Id = ans = tot = 0;
for (int i = 1;
i <= n;
i++)
head[i] = -1, id[i] = match[i] = 0;
}
void add(int u, int v) {
e[++tot].to = v;
e[tot].nxt = head[u];
head[u] = tot;
}
int getf(int x) {
return f[x] == x ? x : f[x] = getf(f[x]);
}
//查询x和y在带花树中的LCA
int LCA(int x, int y) { //沿着增广路向上找lca
for (++Id;
;
swap(x, y)) {//x,y交替向上
if (x) {
x = getf(x);
//有可能环中有环（花中有花），所以用并查集找祖先，只处理祖先节点
if (id[x] == Id)return x;
//x,y在同一环中，一定会找到已被编号的点，该点即为LCA
else id[x] = Id, x = pre[match[x]];
//给点编号，并沿着非匹配边向上找
}
}
}
//缩点（开花），将x,y到LCA(l)路径中的点，缩为一点
void blossom(int x, int y, int l) {
while (getf(x) != l) {//增广路取反
pre[x] = y, y = match[x];
//如果x、y的奇环中有白点，将其染为黑点，放入队列，让其去找不是环中的匹配点
if (vis[y] == 2)vis[y] = 1, q.push(y);
//只改变是根的点
if (getf(x) == x)f[x] = l;
if (getf(y) == y)f[y] = l;
//增光路取反
x = pre[y];
}
}
bool aug(int s) {
for (int i = 1;
i <= n;
i++)
vis[i] = pre[i] = 0, f[i] = i;
while (!q.empty())q.pop();
q.push(s), vis[s] = 1;
while (!q.empty()) {
u = q.front();
q.pop();
for (int i = head[u];
~i;
i = e[i].nxt) {
v = e[i].to;
//如果已经在同一个环（花）中或者是白点（意为这已经有匹配点），直接跳过
//这种情况不会增加匹配数
if (getf(u) == getf(v) || vis[v] == 2)continue;
if (!vis[v]) {
//先染为白色，将前继点指向u
vis[v] = 2, pre[v] = u;
//如果没有被匹配过，直接匹配成功
if (!match[v]) {
for (int x = v, last;
x;
x = last)
last = match[pre[x]], match[x] = pre[x], match[pre[x]] = x;
return 1;
}
//如果被匹配过，则把匹配v的点染为黑色，放入队列中
vis[match[v]] = 1, q.push(match[v]);
}
else {
int lca = LCA(u, v);
blossom(u, v, lca), blossom(v, u, lca);
}
}
}
return 0;
}
int main() {
scanf("%d", &n);
int u, v;
Init();
while (~scanf("%d%d", &u, &v)&&u) {
add(u, v);
add(v, u);
}
for (int i = 1;
i <= n;
i++)
if (!match[i] && aug(i))
ans++;
printf("%d\n", ans*2);
memset(vis, 0, sizeof(vis));
//vis再利用
for (int i = 1;
i <= n;
i++)
if (match[i] && !vis[i]) {
vis[i] = 1;
vis[match[i]] = 1;
printf("%d %d\n", i, match[i]);
}
return 0;
}
HDU 4687 Boke and Tsukkomi
#include
using namespace std;
const int N = 50;
int g[N][N];
int ans, ana[N*N];
int n, m;
queueq;
int Id, id[N],f[N],pre[N],vis[N],match[N];
struct Edge {
int u, v;
}e[N*N];
void Init() {
Id = 0;
for (int i = 1;
i <= n;
i++)id[i] = match[i] = 0;
}
int getf(int x) {
return f[x] == x ? x : f[x] = getf(f[x]);
}
int LCA(int x, int y) {
for (++Id;
;
swap(x, y)) {
if (x) {
x = getf(x);
if (id[x] == Id)return x;
else id[x] = Id, x = pre[match[x]];
}
}
}
void blossom(int x, int y, int l) {
while (getf(x) != l) {
pre[x] = y, y = match[x];
if (vis[y] == 2)vis[y] = 1, q.push(y);
if (getf(x) == x)f[x] = l;
if (getf(y) == y)f[y] = l;
x = pre[y];
}
}
int aug(int s) {
for (int i = 1;
i <= n;
i++)
vis[i] = pre[i] = 0, f[i] = i;
while (!q.empty())q.pop();
q.push(s), vis[s] = 1;
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v = 1;
v <= n;
v++) {
if (!g[u][v]||getf(u)==getf(v)||vis[v]==2)continue;
if (!vis[v]) {
vis[v] = 2, pre[v] = u;
if (!match[v]) {
for (int x = v, last;
x;
x = last)
last = match[pre[x]], match[x] = pre[x], match[pre[x]] = x;
return 1;
}
vis[match[v]] = 1, q.push(match[v]);
}
else {
int lca = LCA(u, v);
blossom(u, v, lca), blossom(v, u, lca);
}
}
}
return 0;
}
int maxmatch() {
Init();
int maxx = 0;
for (int i = 1;
i <= n;
i++)
if (!match[i])maxx += aug(i);
return maxx;
}
int main() {
while (~scanf("%d%d", &n, &m)) {
ans = 0;
memset(g, 0, sizeof(g));
for (int i = 1;
i <= m;
i++) {
scanf("%d%d", &e[i].u, &e[i].v);
g[e[i].u][e[i].v] = g[e[i].v][e[i].u] = 1;
}
int cnt = maxmatch();
for (int i = 1;
i <= m;
i++) {
int u = e[i].u;
int v = e[i].v;
memset(g, 0, sizeof(g));
for (int x, y, j = 1;
j <= m;
j++) {
if (j == i)continue;
x = e[j].u;
y = e[j].v;
if (x == u || y == u || x == v || y == v)continue;
g[x][y] = g[y][x] = 1;
}
int cur = maxmatch();
if (cur < cnt - 1)ana[++ans] = i;
}
printf("%d\n", ans);
for (int i = 1;
i <= ans;
i++)printf(i == 1 ? "%d" : " %d", ana[i]);
printf("\n");
}
return 0;
} 
