二分图

简介

二分图即一个无向图，可以把节点分为两个集合，使得同一个集合内的点之间没有边。

判定可以用DFS/BFS判断是否有奇环，也可以用并查集（拆点，或者关系型并查集）

二分图的最大匹配，比一般图的最大匹配问题简单很多。

二分图匹配
匈牙利算法比较简单，一般使用匈牙利算法

二分图点的标号，左右分开标
左边1号点，右边1号点，不同

匈牙利算法
时间复杂度
一共尝试 n 次
尝试一次的最坏情况，会尝试所有的点和边 O(n + m)
总时间复杂度 O(n m)

刚开始加入右端所有的点
左边的点一个一个加入，加入每个点时找增广路
需要 一个邻接矩阵矩阵 / 链表 / vector数组存边，左右两边的点标号可以一样
需要 match 数组，记录右端的每个点，匹配左端哪个点。
有的人会再开一个数组，记录左边的每个点匹配右边的哪个点，可以但没必要。
需要 visit 数组，表示当前右端的点是否被搜索过。
有的人表示当前左边的点是否被搜搜过。

void dfs(左边点的标号 x) // 左边的x可以找到 右边未被标记的点匹配吗？
{
for (枚举和x相连，右边点的标号i)
{
if (i没有被搜索过)
{
标记i已经被搜索过
if (右边的i不匹配任何左边的点 || 右边的i匹配的左边的点可以调整)
{
右边的i匹配左边的x
return true; 左边的x找到了可以匹配点
}
}
}
return false; 找不到
}

Konig's theorem:

最大独立集：选择尽量多的点，使得选择的点之间不要有边
最大独立集 = 两边点数之和 - 最大匹配

最小点覆盖：选择尽量少的点，使得每条边至少一个端点被选
最小点覆盖 = 最大匹配

最小点覆盖 >= 最大匹配
匹配中每一条边一定选一个端点

最小点覆盖 <= 最大匹配

最小边覆盖：选择最少的边，覆盖所有的点
最小边覆盖 = 最大独立集

Hall's marriage theorem

如果左边任选一个子集L，右边与L中点相邻的点的子集是R
如果对于任意L，得到 R的大小 都 >= L的大小
那么这个图最大匹配是L的大小

推论：
两边都有n个点
所有点度数相同
那么一定有完美匹配

Dilworth's theorem
有向无环图中
最小链覆盖 = 最长反链

最小链覆盖 （链可以相交，同一个点可以被多条链覆盖）
最小路径覆盖 （路径不可以相交，同一个点不可以被多条路径覆盖）

反链：最大的点的子集，任意2个点不能互相到达。

最小链覆盖 做一次Floyd（传递闭包），转化为 最小路径覆盖

最小路径覆盖 = n - 自己对自己的最大匹配

Dilworth's theorem
用最少的不下降子序列 覆盖一个序列 至少需要几个？
答案是 最长下降子序列的长度

匈牙利算法

计算二分图最大匹配的一个方法

值得注意的是左右两个集合中的点，标号可以相同。

最简单的思路，枚举左侧的每个点，在自己接受的右侧的集合随机选一个，相当于直接贪心（很可能不是最优解）

找交错轨，

交错轨(alternating path)是图的一条简单路径，满足任意相邻的两条边，一条在匹配内， 一条不在匹配内。
增广轨(augmenting path)是一个始点与终点都为未匹配点的交错轨

#include<iostream>
using namespace std;
int n,l[520],v[520],g[520][520];
int i,j,k,ans;
int dfs(int x)
{
    for(int i=1;i<=n;i++)
        if(!v[i]&&g[x][i])
        {
            v[i]=1;
            if(l[i]==-1||dfs(l[i]))
            {
                l[i]=x;
                return 1;
            }
        }
    return 0;
}
int main()
{
    cin>>n>>k;
    while(k--)
    {
        scanf("%d%d",&i,&j);
        g[i][j]=1;
    }
    memset(l,-1,sizeof(l));
    for(i=1;i<=n;i++)
    {
        memset(v,0,sizeof(v));
        if(dfs(i))
        ans++;
    }
    printf("%d",ans);
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[220];
int v[220], l[220];
// v[i] 右边的第i个点是否尝试过
// l[i] 右边的第i个点 匹配左侧的哪个点？ 如果右边的第i个点 不在匹配中 那么为0
bool dfs(int x) // x 是左侧的点
{
    for (int i: a[x]) // 枚举和 x 相邻的右边的点
    {
        if (!v[i]) // 如果这个右边的点没有尝试过
        {
            v[i] = true; // 标记上这个点尝试过了
            if (l[i] == 0 || dfs(l[i])) // 如果右边的第i个点 不在匹配中 或者 右边的第i个点在匹配中，但是可以调整
            {
                l[i] = x; // 让右边的第i个点匹配左边的第j个点
                return true; // 匹配成功
            }
        }
    }
    return false;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
    {
        int l;
        scanf("%d", &l);
        a[i].resize(l);
        for (int j = 0; j < l; j++)
        {
            scanf("%d", &a[i][j]);
        }
    }
    int z = 0;
    for (int i = 1; i <= n; i++)
    {
        memset(v, 0, sizeof v);
        if (dfs(i))
        {
            z++;
        }
    }
    printf("%d\n", z);
    return 0;
}

时间复杂度

最坏情况下，每次增广都要DFS整个图 时间复杂度是 $O(n + m)$

一共增广点数次 时间复杂度是 $O(n (n + m))$。

一些重要的结论

最小链覆盖(多条链可以重叠)
最小路径覆盖(多条路径不可以有公共点)
最小链覆盖跑一下传递闭包就只需要求最小路径覆盖了。
最小链覆盖 = 最长反链

最小路径覆盖：如果原图中有一条x到y的边，
新建一个二分图，左侧的x到右侧的y
点数减去新二分图的最大匹配，就是最小路径覆盖的答案

最小点覆盖:选出一个点集，使得每条边至少有一个端点被选择。

最小支配集:选出一个点集，使得每个点要么被选择，要么和被选择的点有边相连。

补图是二分图的最大团
等价于
二分图的最大独立集
等价于
左边点数 + 右边点数 - 最大匹配。

二分图最小点覆盖 等于 最大匹配

棋盘覆盖

给定一个 N 行 N 列的棋盘，已知某些格子禁止放置。
求最多能往棋盘上放多少块的长度为 2、宽度为 1 的骨牌，骨牌的边界与格线重合（骨牌占用两个格子），并且任意两张骨牌都不重

这个棋盘是二分图
如果行数加列数是奇数，认为在二分图的左边
如果行数加列数是偶数，认为在二分图的右边
相邻的两个格子一定一左一右，认为他们之间有一条边
如果想知道最多的块数，就做二分图匹配

问最多选多少个格子，不互相相邻？
相当于上一个二分图的最大独立集
所以就是所有空位数减去最大匹配数

参考题目

P1894 [USACO4.2]完美的牛栏The Perfect Stall

https://www.luogu.com.cn/problem/P1894

题目描述

农夫约翰上个星期刚刚建好了他的新牛棚，他使用了最新的挤奶技术。

不幸的是，由于工程问题，每个牛栏都不一样。

第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。

上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。

一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。

给出奶牛们的爱好的信息，计算最大分配方案。

输入格式

第一行为两个整数，$n$ 和 $m$。$n$ 是农夫约翰的奶牛数量，$m$ 是新牛棚的牛栏数量。

第二行到第 $n+1$ 行 一共 $n$ 行，每行对应若干个整数一只奶牛。第一个数字 $s_i$ 是这头奶牛愿意在其中产奶的牛栏的数目。后面的 $s_i$ 个数表示这些牛栏的编号。牛栏的编号限定在区间 $[1,m]$ 中，在同一行，一个牛栏不会被列出两次。

输出格式

只有一行，为一个整数，表示最多能分配到的牛栏的数量。

样例 #1

样例输入 #1

5 5
2 2 5
3 2 3 4
2 1 5
3 1 2 5
1 2

样例输出 #1

4

提示

$0\le n,m\le 200$，$0\le s_i\le m$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[220];
int v[220], l[220];
bool dfs(int x)
{
	for (int i: a[x])
	{
		if (!v[i])
		{
			v[i] = true;
			if (l[i] == 0 || dfs(l[i]))
			{
				l[i] = x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		int l;
		scanf("%d", &l);
		a[i].resize(l);
		for (int j = 0; j < l; j++)
		{
			scanf("%d", &a[i][j]);
		}
	}
	int z = 0;
	for (int i = 1; i <= n; i++)
	{
		memset(v, 0, sizeof v);
		if (dfs(i))
		{
			z++;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

P2071 座位安排

https://www.luogu.com.cn/problem/P2071

题目背景

公元二零一四年四月十七日，小明参加了省赛，在一路上，他遇到了许多问题，请你帮他解决。

题目描述

已知车上有N排座位，有N*2个人参加省赛，每排座位只能坐两人，且每个人都有自己想坐的排数，问最多使多少人坐到自己想坐的位置。

输入格式

第一行，一个正整数Ｎ。

第二行至第Ｎ*2+1行，每行两个正整数Si1，Si2，为每个人想坐的排数。

输出格式

一个非负整数，为最多使得多少人满意。

样例 #1

样例输入 #1

4
1 2
1 3
1 2
1 3
1 3
2 4
1 3
2 3

样例输出 #1

7

提示

对于10%的数据 N≤10

对于30%的数据 N≤50

对于60%的数据 N≤200

对于100%的数据 N≤2000

算法提示：二分图的最大匹配

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> a[4020];
int v[4020], l[4020];
bool dfs(int x)
{
	for (int i: a[x])
	{
		if (!v[i])
		{
			v[i] = true;
			if (l[i] == 0 || dfs(l[i]))
			{
				l[i] = x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= 2 * n; i++)
	{
		a[i].resize(4);
		scanf("%d%d", &a[i][0], &a[i][1]);
		a[i][2] = a[i][0] + n;
		a[i][3] = a[i][1] + n;
	}
	int z = 0;
	for (int i = 1; i <= 2 * n; i++)
	{
		memset(v, 0, sizeof v);
		if (dfs(i))
		{
			z++;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

P2756 飞行员配对方案问题

https://www.luogu.com.cn/problem/P2756

题目背景

第二次世界大战期间，英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的两名飞行员，其中一名是英国飞行员，另一名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。

题目描述

一共有 $n$ 个飞行员，其中有 $m$ 个外籍飞行员和 $(n - m)$ 个英国飞行员，外籍飞行员从 $1$ 到 $m$ 编号，英国飞行员从 $m + 1$ 到 $n$ 编号。 对于给定的外籍飞行员与英国飞行员的配合情况，试设计一个算法找出最佳飞行员配对方案，使皇家空军一次能派出最多的飞机。

输入格式

输入的第一行是用空格隔开的两个正整数，分别代表外籍飞行员的个数 $m$ 和飞行员总数 $n$。
从第二行起到倒数第二行，每行有两个整数 $u, v$，代表外籍飞行员 $u$ 可以和英国飞行员 $v$ 配合。
输入的最后一行保证为 -1 -1，代表输入结束。

输出格式

本题存在 Special Judge。
请输出能派出最多的飞机数量，并给出一种可行的方案。
输出的第一行是一个整数，代表一次能派出的最多飞机数量，设这个整数是 $k$。
第 $2$ 行到第 $k + 1$ 行，每行输出两个整数 $u, v$，代表在你给出的方案中，外籍飞行员 $u$ 和英国飞行员 $v$ 配合。这 $k$ 行的 $u$ 与 $v$ 应该互不相同。

样例 #1

样例输入 #1

5 10
1 7
1 8
2 6
2 9
2 10
3 7
3 8
4 7
4 8
5 10
-1 -1

样例输出 #1

4
1 7
2 9
3 8
5 10

提示

【数据范围与约定】

• 对于 $100\%$ 的数据，保证 $1 \leq m \leq n < 100$，$1 \leq u \leq m < v \leq n$，同一组配对关系只会给出一次。

【提示】

• 请注意输入的第一行先读入 $m$，再读入 $n$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z;
vector<int> a[120];
int v[120], l[120];
bool dfs(int x)
{
	for (int i : a[x])
	{
		if (!v[i])
		{
			v[i] = true;
			if (l[i] == 0 || dfs(l[i]))
			{
				l[i] = x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d%d", &n, &m);
	while (true)
	{
		scanf("%d%d", &x, &y);
		if (x == -1 && y == -1)
		{
			break;
		}
		a[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
	{
		memset(v, 0, sizeof v);
		if (dfs(i))
		{
			z++;
		}
	}
	printf("%d\n", z);
	for (int i = n + 1; i <= m; i++)
	{
		if (l[i])
		{
			printf("%d %d\n", l[i], i);
		}
	}
	return 0;
}

题解

P3033 [USACO11NOV]Cow Steeplechase G

https://www.luogu.com.cn/problem/P3033

题目描述

Farmer John has a brilliant idea for the next great spectator sport: Cow Steeplechase! As everyone knows, regular steeplechase involves a group of horses that race around a course filled with obstacles they must jump over. FJ figures the same contest should work with highly-trained cows, as long as the obstacles are made short enough.

In order to design his course, FJ makes a diagram of all the N (1 <= N <= 250) possible obstacles he could potentially build. Each one is represented by a line segment in the 2D plane that is parallel to the horizontal or vertical axis. Obstacle i has distinct endpoints (X1_i, Y1_i) and (X2_i, Y2_i) (1 <= X1_i, Y1_i, X2_i, Y2_i <= 1,000,000,000). An example is as follows:

   --+-------   
-----+-----
  ---+---     |
     |     |  |
   --+-----+--+-   |
     |     |  |  | |
     |   --+--+--+-+-
           |  |  | |
              |

FJ would like to build as many of these obstacles as possible, subject to the constraint that no two of them intersect. Starting with the diagram above, FJ can build 7 obstacles:

   ----------   
-----------
  -------     |
           |  |
           |  |    |
           |  |  | |
           |  |  | |
           |  |  | |
              |

Two segments are said to intersect if they share any point in common, even an endpoint of one or both of the segments. FJ is certain that no two horizontal segments in the original input diagram will intersect, and that similarly no two vertical segments in the input diagram will intersect.

Please help FJ determine the maximum number of obstacles he can build.

给出N平行于坐标轴的线段，要你选出尽量多的线段使得这些线段两两没有交点（顶点也算），横的与横的，竖的与竖的线段之间保证没有交点，输出最多能选出多少条线段。

输入格式

* Line 1: A single integer: N.

* Lines 2..N+1: Line i+1 contains four space-separated integers representing an obstacle: X1_i, Y1_i, X2_i, and Y2_i.

输出格式

* Line 1: The maximum number of non-crossing segments FJ can choose.

样例 #1

样例输入 #1

3 
4 5 10 5 
6 2 6 12 
8 3 8 5 

样例输出 #1

2 

提示

There are three potential obstacles. The first is a horizontal segment connecting (4, 5) to (10, 5); the second and third are vertical segments connecting (6, 2) to (6, 12) and (8, 3) to (8, 5).

The optimal solution is to choose both vertical segments.

参考代码

#include <bits/stdc++.h>
using namespace std;
int n;
int xa[252];
int ya[252];
int xb[252];
int yb[252];
int v[252];
int l[252];
bool dfs(int i)
{
	for (int j = 1; j <= n; j++)
	{
		if (ya[j] == yb[j] && ya[i] <= ya[j] && yb[j] <= yb[i] && xa[j] <= xa[i] && xb[i] <= xb[j] && !v[j])
		{
			v[j] = true;
			if (l[j] == 0 || dfs(l[j]))
			{
				l[j] = i;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d%d%d%d", &xa[i], &ya[i], &xb[i], &yb[i]);
		if (xa[i] > xb[i])
		{
			swap(xa[i], xb[i]);
		}
		if (ya[i] > yb[i])
		{
			swap(ya[i], yb[i]);
		}
	}
	int z = 0;
	for (int i = 1; i <= n; i++)
	{
		if (xa[i] == xb[i])
		{
			memset(v, 0, sizeof v);
			if (dfs(i))
			{
				z++;
			}
		}
	}
	printf("%d\n", n - z);
	return 0;
}

题解

P3386 【模板】二分图最大匹配

https://www.luogu.com.cn/problem/P3386

题目描述

给定一个二分图，其左部点的个数为 $n$，右部点的个数为 $m$，边数为 $e$，求其最大匹配的边数。

左部点从 $1$ 至 $n$ 编号，右部点从 $1$ 至 $m$ 编号。

输入格式

输入的第一行是三个整数，分别代表 $n$，$m$ 和 $e$。

接下来 $e$ 行，每行两个整数 $u, v$，表示存在一条连接左部点 $u$ 和右部点 $v$ 的边。

输出格式

输出一行一个整数，代表二分图最大匹配的边数。

样例 #1

样例输入 #1

1 1 1
1 1

样例输出 #1

1

样例 #2

样例输入 #2

4 2 7
3 1
1 2
3 2
1 1
4 2
4 1
1 1

样例输出 #2

2

提示

数据规模与约定

对于全部的测试点，保证：

• $1 \leq n, m \leq 500$。
• $1 \leq e \leq 5 \times 10^4$。
• $1 \leq u \leq n$，$1 \leq v \leq m$。

不保证给出的图没有重边。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z;
vector<int> a[520];
int v[520], l[520];
bool dfs(int x)
{
	for (int i : a[x])
	{
		if (!v[i])
		{
			v[i] = true;
			if (l[i] == 0 || dfs(l[i]))
			{
				l[i] = x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d%*d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
	{
		memset(v, 0, sizeof v);
		if (dfs(i))
		{
			z++;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

P7368 [USACO05NOV]Asteroids G

https://www.luogu.com.cn/problem/P7368

题目描述

贝茜想在 $N\times N$ 的网格中驾驶她的宇宙飞船。网格中有 $K$ 个小行星。要使驾驶过程愉快，就必须把这些小行星全部消除。

贝茜有一个武器，可以以一个单位代价消除一行或一列的全部小行星。贝茜想问你，要把所有小行星都消除的最小代价是多少。

输入格式

第一行两个整数 $N,K$。

接下来 $K$ 行，每行输入 $x_i,y_i$，表示第 $i$ 个小行星在网格的坐标。

输出格式

一行一个整数，表示把所有小行星消除的最小代价。

样例 #1

样例输入 #1

3 4
1 1
1 3
2 2
3 2

样例输出 #1

2

提示

样例解释：

样例的图为（X 为小行星）：

X.X
.X.
.X.

贝茜可以分别消除第一行和第二列的小行星。

---

数据范围：

对于 $100\%$ 的数据，$1 \leq N \leq 500$，$1 \leq K \leq N \times N$。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, x, y, z;
vector<int> a[520];
int v[520], l[520];
bool dfs(int x)
{
	for (int i : a[x])
	{
		if (!v[i])
		{
			v[i] = true;
			if (l[i] == 0 || dfs(l[i]))
			{
				l[i] = x;
				return true;
			}
		}
	}
	return false;
}
int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++)
	{
		scanf("%d%d", &x, &y);
		a[x].push_back(y);
	}
	for (int i = 1; i <= n; i++)
	{
		memset(v, 0, sizeof v);
		if (dfs(i))
		{
			z++;
		}
	}
	printf("%d\n", z);
	return 0;
}

题解

P2423 [HEOI2012]朋友圈

https://www.luogu.com.cn/problem/P2423

题目背景

原 双塔 请做P1651

题目描述

在很久很久以前，曾经有两个国家和睦相处，无忧无虑的生活着。

一年一度的评比大会开始了，作为和平的两国，一个朋友圈数量最多的永远都是最值得他人的尊敬，所以现在就是需要你求朋友圈的最大数目。两个国家看成是AB两国，现在是两个国家的描述：

A国：每个人都有一个友善值，当两个A国人的友善值 $a,b$，如果 $a\text{ xor}\text{ }b \bmod 2=1$，那么这两个人都是朋友，否则不是；

B国：每个人都有一个友善值，当两个B国人的友善值 $a,b$，如果 $a\text{ xor}\text{ }b \bmod 2=0$ 或者 ($a\text{ }or\text{ }b$) 化成二进制有奇数个 $1$，那么两个人是朋友，否则不是朋友；

A、B两国之间的人也有可能是朋友，数据中将会给出A、B之间“朋友”的情况。
对于朋友的定义，关系是是双向的。
在AB两国，朋友圈的定义：一个朋友圈集合 $S$，满足

$S \subset A \cup B$，对于所有的 $i,j \in S$，$i$ 和 $j$ 是朋友。

由于落后的古代，没有电脑这个也就成了每年最大的难题，而你能帮他们求出最大朋友圈的人数吗？

输入格式

第一行一个整数 $T$（$T\le 6$）,表示输入数据总数。

对于每组数据：

第一行三个整数 $A,B,M$，分别表示A国人数，B国人数，AB两国之间是朋友的对数。

第二行A个数 $a_i$，表示A国第 $i$ 个人的友善值。

第三行B个数 $b_i$，表示B国第 $i$ 个人的友善值。

第 $4$ 到第 $3+M$ 行，每行两个整数 $x,y$ 表示A国的第 $x$ 个人和B国第 $y$ 个人是朋友。

输出格式

输出 $T$ 行，每行输出一个整数，表示最大朋友圈的数目。

样例 #1

样例输入 #1

1
2 4 7
1 2
2 6 5 4
1 1
1 2
1 3
2 1
2 2
2 3
2 4

样例输出 #1

5

提示

最大朋友圈包含A国第 $1,2$ 人和B国第 $1,2,3$ 人。

友善值为 int 类型正整数。

有两类数据：

第一类：$|A| \leq 200, |B| \leq 200$；

第二类：$|A| \leq 10, |B| \leq 3000$。

参考代码

题解

A是一个二分图，所以在最大团中可能选0个A，1个A，2个A
A的选取情况，直接枚举即可
枚举之后，只保留和A中枚举的右边的B

P1640 [SCOI2010] 连续攻击游戏

https://www.luogu.com.cn/problem/P1640

题目描述

lxhgww 最近迷上了一款游戏，在游戏里，他拥有很多的装备，每种装备都有 $2$ 个属性，这些属性的值用 $[1,10000]$ 之间的数表示。当他使用某种装备时，他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后，lxhgww 遇到了终极 boss，这个终极 boss 很奇怪，攻击他的装备所使用的属性值必须从 $1$ 开始连续递增地攻击，才能对 boss 产生伤害。也就是说一开始的时候，lxhgww 只能使用某个属性值为 $1$ 的装备攻击 boss，然后只能使用某个属性值为 $2$ 的装备攻击 boss，然后只能使用某个属性值为 $3$ 的装备攻击 boss……以此类推。现在 lxhgww 想知道他最多能连续攻击 boss 多少次？

输入格式

输入的第一行是一个整数 $N$，表示 lxhgww 拥有 $N$ 种装备接下来 $N$ 行，是对这 $N$ 种装备的描述，每行 $2$ 个数字，表示第 $i$ 种装备的 $2$ 个属性值。

输出格式

输出一行，包括 $1$ 个数字，表示 lxhgww 最多能连续攻击的次数。

样例 #1

样例输入 #1

3
1 2
3 2
4 5

样例输出 #1

2

提示

对于 $30\%$ 的数据，保证 $N \le 10^3$。

对于 $100\%$ 的数据，保证 $N \le 10^6$。

参考代码

题解

每个属性建一个点，每个装备合并两个点
每个属性的连通块需要记录
这个连通块内属性的个数
这个连通块内装备的个数
这个连通块内最大的属性

从1到10000依次验证每个属性能否获得，获得的条件是
属性连通块内 装备的个数 >= 属性的个数 或 当前枚举的属性 < 连通块内最大的属性

P4298 [CTSC2008]祭祀

https://www.luogu.com.cn/problem/P4298

题目描述

在遥远的东方，有一个神秘的民族，自称Y族。他们世代居住在水面上，奉龙王为神。每逢重大庆典， Y族都会在水面上举办盛大的祭祀活动。我们可以把Y族居住地水系看成一个由岔口和河道组成的网络。每条河道连接着两个岔口，并且水在河道内按照一个固定的方向流动。显然，水系中不会有环流（下图描述一个环流的例子）。

由于人数众多的原因，Y族的祭祀活动会在多个岔口上同时举行。出于对龙王的尊重，这些祭祀地点的选择必须非常慎重。准确地说，Y族人认为，如果水流可以从一个祭祀点流到另外一个祭祀点，那么祭祀就会失去它神圣的意义。族长希望在保持祭祀神圣性的基础上，选择尽可能多的祭祀的地点。

输入格式

第一行包含两个用空格隔开的整数N、M，分别表示岔口和河道的数目，岔口从1到N编号。

接下来M行，每行包含两个用空格隔开的整数u、v，描述一条连接岔口u和岔口v的河道，水流方向为自u向v。

输出格式

第一行包含一个整数K，表示最多能选取的祭祀点的个数。
接下来一行输出一种可行的选取方案。对于每个岔口依次输出一个整数，如果在该岔口设置了祭祀点，那么输出一个1，否则输出一个0。应确保你输出的1
的个数最多，且中间没有空格。
接下来一行输出，在选择最多祭祀点的前提下，每个岔口是否能够设置祭祀点。对于每个岔口依次输出一个整数，如果在该岔口能够设置祭祀点，那么输出一个
1，否则输出一个0。
注意：多余的空格和换行可能会导致你的答案被判断为错误答案。

样例 #1

样例输入 #1

4 4
1 2
3 4
3 2
4 2

样例输出 #1

2
1010
1011

提示

N ≤ 100 M ≤ 1 000

在样例给出的水系中，不存在一种方法能够选择三个或者三个以上的祭祀点。包含两个祭祀点的测试点的方案有两种：

选择岔口1与岔口3（如样例输出第二行），选择岔口1与岔口4。

水流可以从任意岔口流至岔口2。如果在岔口2建立祭祀点，那么任意其他岔口都不能建立祭祀点但是在最优的一种祭祀点的选取方案中我们可以建立两个祭祀点，所以岔口2不能建立祭祀点。对于其他岔口至少存在一个最优方案选择该岔口为祭祀点，所以输出为1011。

感谢@ACdreamer 提供SPJ

参考代码

题解

P1129 [ZJOI2007] 矩阵游戏

https://www.luogu.com.cn/problem/P1129

题目描述

小 Q 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个 $n \times n$ 黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：

• 行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）。
• 列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）。

游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。

对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小 Q 决定写一个程序来判断这些关卡是否有解。

输入格式

本题单测试点内有多组数据。

第一行包含一个整数 $T$，表示数据的组数，对于每组数据，输入格式如下：

第一行为一个整数，代表方阵的大小 $n$。
接下来 $n$ 行，每行 $n$ 个非零即一的整数，代表该方阵。其中 $0$ 表示白色，$1$ 表示黑色。

输出格式

对于每组数据，输出一行一个字符串，若关卡有解则输出 Yes，否则输出 No。

样例 #1

样例输入 #1

2
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0

样例输出 #1

No
Yes

提示

数据规模与约定

• 对于 $20\%$ 的数据，保证 $n \leq 7$。
• 对于 $50\%$ 的数据，保证 $n \leq 50$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 200$，$1 \leq T \leq 20$。

参考代码

题解

poj 3692

SP4206 MATCHING - Fast Maximum Matching

参考资料

二分图 Wikipedia