二分图（一）

$\newcommand \m \mathbf$

$\text{By DaiRuiChen07}$

一、二分图匹配基础

I. 匹配的概念

在一张无向图 $\m G=(\m V,\m E)$ 中，如果 $\m M\subseteq \m E$ 是 $\m G$ 的一个匹配，当且仅当 $\m M$ 中没有两条边有相同的顶点

以下记 $V(\m M)$ 表示 $\m M$ 中的边的顶点构成的点集

一个匹配的大小定义为 $|\m M|$

类似的，在一张带权无向图上，$\m M$ 的权值为 $\sum_{e\in\m M}w(e)$，其中 $w(e)$ 表示 $e$ 的边权

II. 增广轨与交错轨

交错轨是 $\m G$ 中的一条简单路径，其中路径上在 $\m M$ 中和不在 $\m M$ 的边交替出现

增广轨（Augmenting Path）是一种特殊的交错轨，满足其两端的边和其两端的顶点都不在 $\m M$ 中

增广轨有一个很优秀的性质：

如果令某条增广轨为 $\m A$，那么 $\m M\oplus\m A$ 也是一个匹配

且 $|\m M\oplus \m A|=|\m M|+1$

二、增广轨算法

I. 算法流程

以上为代码不仅适用于二分图的最大匹配，同时也适用于一般图的最大匹配

II. 正确性证明

我们需要证明，当 $\m G$ 中没有 $\m M$ 的增广轨的时候，$\m M$ 为 $\m G$ 的一个最大匹配

证：

反证法，假设存在另一个匹配 $\m {M'}$ 使得 $|\m M'|>|\m M|$

考虑一张子图 $\m{G'}=\m{M'}\oplus\m M$，注意到其中的每个点度数最多为 $2$，因此 $\m G'$ 只能由若干环、链和点组成

显然，由于 $\m {G'}$ 中的若干个连通块都必然是交替出现 $\m M$ 和 $\m M'$ 中的边，因此 $\m {G'}$ 中不可能出现奇环

注意到：在一个偶环中，$\m M$ 中的边和 $\m {M'}$ 中的的边的数量是相等的

因此 $\m G'$ 中必然要有一条链，使得其头尾的边都在 $\m{M'}$ 中

那么此时这条链会构成一条交错路 $\m A$，要证明 $\m A$ 是 $\m M$ 的一条增广轨，我们可以还需要证明 $\m A$ 的两端不在 $V(\m M)$ 中

这是显然的，因为如果其中一端存在一条边 $e\in\m M,e\not\in\m{G'} $ 那么我们可以推知 $e\in \m{M’}$，但是此时这个端点在 $\m {M'}$ 中引出了两条边，显然是不成立的

因此此时存在一条关于 $\m M$ 的增广轨，故原命题得证

III. 如何找增广轨

令二分图 $\m G=(\m X,\m Y,\m E)$，其中 $\m X$ 为左部点点集（点为 $\{x_i\}$），$\m Y$ 为右部点点集（点为 $\{y_i\}$）

定义一个集合 $\m S$ 维护此时某条交错轨的终点，朴素的算法流程如下：

这样暴力找增广轨的复杂度 $\Theta(n+m)$，由于我们一般认为 $m\ge n$，所以这样的总复杂度是 $\Theta(nm)$

IV. 习题演练

SGU190 - Dominoes

考虑对于原本的棋盘做黑白间隔染色，那么每个骨牌一定覆盖两个相邻的异色格子，因此把黑白色的格子分别看成左部点和右部点，相邻的格子连边，可以变成一张二分图

然后只需要跑一遍二分图最大匹配，选择的边对应为覆盖其两个顶点的一个骨牌，只需要判断是否覆盖满了即可

注意到做法自动带匹配方案，因此输出很简单

代码如下：

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int MAXN=1601,MAXS=41;
vector <int> edge[MAXN];
int n,k;
int tar[MAXN],dx[]={0,0,1,-1},dy[]={1,-1,0,0};
bool vis[MAXN],a[MAXS][MAXS];
inline int id(int x,int y) {
	if(x<1||x>n||y<1||y>n||a[x][y]) return -1;
	return (x-1)*n+y;
}
inline int getx(int id) {
	return ((id-1)/n)+1;
}
inline int gety(int id) {
	return id-(getx(id)-1)*n;
}
inline bool match(int p) {
	for(int x:edge[p]) {
		if(vis[x]) continue;
		vis[x]=true;
		if(tar[x]==-1||match(tar[x])) {
			tar[x]=p;
			return true;
		}
	}
	return false;
}
inline void print(vector <pii> data) {
	printf("%d\n",(int)data.size());
	for(auto x:data) printf("%d %d\n",x.first,x.second);
}
signed main() {
	memset(tar,-1,sizeof(tar));
	scanf("%d%d",&n,&k);
	for(int i=1;i<=k;++i) {
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=1;
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(id(i,j)==-1||(i+j)%2==0) continue;
			for(int k:{0,1,2,3}) {
				int x=i+dx[k],y=j+dy[k];
				if(id(x,y)!=-1) {
					edge[id(i,j)].push_back(id(x,y));
				}
			}
		}
	}
	int ret=0;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(id(i,j)==-1||(i+j)%2==0) continue;
			memset(vis,false,sizeof(vis));
			if(match(id(i,j))) ++ret;
		}
	}
	if(ret*2+k!=n*n) {
		puts("No");
		return 0;
	}
	puts("Yes");
	vector <pii> her,ver;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(id(i,j)==-1||(i+j)%2==1) continue;
			int x=getx(tar[id(i,j)]),y=gety(tar[id(i,j)]);
			if(x==i) her.push_back(make_pair(x,min(j,y)));
			else ver.push_back(make_pair(min(i,x),y));
		}
	}
	print(ver);
	print(her);
	return 0;
}

三、Hall 定理

I. 二分图的邻域

对于一张二分图 $\m G=(\m X,\m Y,\m E)$

对于点集 $\m A\subseteq \m X$，$N(\m A)=\{y_i|\exists x_j:(x_j,y_i)\in\m E\}$

即所有与 $\m A$ 中的某个点 $x_j$ 相连的 $y_i$ 组成的集合记为 $N(\m A)$，即 $\m A$ 的邻域

II. Hall 定理

$\m G$ 中有一个大小为 $|\m X|$ 的匹配 $\iff$ $\forall \m A\subseteq \m S:|N(\m A)|\ge |\m A|$

III. 证明

充分性显然：$N(\m A)$ 中一定包含所有 $\m A$ 中通过匹配边连接的右部点，故 $|N(\m A)|\ge|\m A|$

下证必要性：

证：

原命题较难，考虑其逆否命题

即：对于 $\m G$ 的最大匹配 $\m M$，我们有 $|\m X|>|\m M|$，即某个大小为 $|\m X|$ 的边集 $\m K$ 不是 $\m G$ 的一个匹配

那么可以推出 $\exists\m A\subseteq \m K:|N(\m A)|< |\m A|$

考虑对匹配 $\m M$ 运行一遍查找增广路的算法，那么此时得到上述的集合 $\m S$

我们记 $\m{S_X}=\m S\cap \m X$，$\m{T_X}=\overline{\m{S_X}}$，$\m {S_Y}=\m S\cap\m Y$，$\m{T_Y}=\overline{\m{S_Y}}$

我们大概的思路是：

首先：证明 $N(\m{S_X})=\m{S_Y}$，可以转化为不存在连接 $\m{S_X}$ 和 $\m{T_Y}$ 的边

然后，我们证明 $|\m {S_X}|>|\m {S_Y}|$

引理一：$N(\m{S_X})=\m{S_Y}$

不存在 $\m M$ 中的，连接 $\m{S_X}$ 和 $\m{T_Y}$ 的边
显然，考虑 $\m {S_X}$ 的生成过程，如果某个 $x\in\m{S_X}$，那么必然有以下两种情况之一：

$x$ 没有连接 $\m M$ 的边

$x$ 通过某条 $\m M$ 里面的边和某个 $\m{S_Y}$ 里面的点相连

这两种情况都是不可能出现在某条连接 $\m{S_X}$ 和 $\m{S_Y}$ 的边当中的

不存在不在 $\m M$ 中的，连接 $\m{S_X}$ 和 $\m{T_Y}$ 的边

考虑 $\m{T_Y}$ 的生成过程，假如某个 $y\in \m{T_Y}$ 考虑某一次从 $\m{S_X}$ 中拓展若干个节点到 $\m {S_Y}$ 的过程，有：

$\not\exists (x,y)\in \m E:x\in\m{S_X}$，显然这样也是矛盾的

综上所述不存在连接 $\m {S_X}$ 和 $\m{S_Y}$ 的边

故 $N(\m{S_X})=\m{S_Y}$

引理二：$|\m{S_Y}|<|\m {S_X}|$

考虑到 $\m{S_Y}$ 的生成过程，显然每个 $y\in\m{S_Y}$ 都可以通过一条 $\m M$ 中的边和某个 $\m{S_X}$ 中的点相连，故 $|\m {S_Y}|\le|\m{S_X}|$

同时，由于我们的假设 $|\m M|<|\m X|$，因此必然有某个 $x\in\m{S_X}$ 使得所有与 $x$ 相连的边都不在 $\m M$ 中，那么我们就证明了 $|\m{S_Y}|$ 严格小于 $|\m {S_X}|$

综合以上结论：我们可以证明出必要性的逆否命题成立，显然得到必要性的证明

综上所述，原命题得证

IV. 应用

一般来说，Hall 定理常用于证明某中特殊的二分图有完美匹配（满足 $V(\m M)=\m V$ 的一个匹配）

例如：对于二分图 $\m G=(\m X,\m Y,\m E)$，其中每个节点的度数都为 $k$，求证：这个二分图一定有一个完美匹配（大小为 $|\m X|$ 的一个匹配）

证：

根据 Hall 定理，原命题 $\iff$ $\forall \m A\subseteq\m X:|\m A|\le|N(\m A)|$

采用反证法，假设存在 $\m A\subseteq\m X:|\m A|>|N(\m A)|$

易得 $|N(\m A)|$ 中所有点的度的和为 $k\cdot|\m A|$

因此，至少存在一个点 $y\in N(\m A)$ 使得 $\operatorname{deg}(u)\ge\dfrac{k\cdot|\m A|}{|N(\m A)|}$

注意到 $\dfrac{k\cdot|\m A|}{|N(\m A)|}>\dfrac{k\cdot|\m A|}{|\m A|}=k$

因此存在 $u\in \m V:\operatorname{deg}(u)>k$，显然矛盾

故原命题得证

V. 习题演练

定义“拉丁方”是一个 $n\times n$ 的矩阵，其中每一行每一列都是一个 $1\sim n$ 的排列

现在这个拉丁方的前 $k$ 行已经填好，且目前这个拉丁方没有出现不合法的地方

求证：无论这个拉丁方的前 $k$ 行填成什么样，总是有至少一个解能够补全这个拉丁方使其完全合法

证明如下：

考虑对于第一列到第 $n$ 列 $C_1\sim C_n$ 当成左部点，而 $1\sim n$ 当成右部点，如果目前第 $i$ 列中没有出现过 $j$ 就连接 $(C_i,j)$

显然，这是一张二分图，且二分图上的某条边 $(C_i,j)$ 代表 $k+1$ 行第 $i$ 列填上 $j$

那么这张二分图上的一个大小为 $n$ 的匹配就代表了第 $k+1$ 行的某一种可能的填法

注意到二分图中每个点的度都是 $n-k$，因此根据上面证明的 Hall 定理的推论，一定有一个大小为 $n$ 的匹配

故我们可以得到第 $k+1$ 行的一种合法填法，此时另 $k\gets k+1$ 继续操作即可最终得到一个合法的拉丁方，证毕

实际上上面的证明给出了一种 $\Theta(n^3)$ 填补完成拉丁方的一种做法

四、Konig 定理

I. 独立集

对于某个 $\m X\subseteq \m V$，若满足 $\forall u,v\in\m X:(u,v)\not\in \m E$

即 $\m X$ 中没有两个点直接相连，则称 $\m X$ 是 $\m V$ 的一个独立集（Independent Set，简称 IS）

II. 覆盖集

对于某个 $\m X\in\m V$，若满足 $\forall (u,v)\in \m E:u\in \m X\lor v\in \m X$

即每条边都至少与 $\m X$ 中的一个点相连，则称 $\m X$ 是 $\m V$ 的一个覆盖集（Vertex Cover，简称 VC）

III. 最小覆盖集与最大独立集

记 $\m{IS}$ 为 $\m G$ 中的一个独立集，$\m {VC}$ 为 $\m G$ 中的一个覆盖集

则有 $\overline{\m{IS}}$ 为一个 $\m G$ 的覆盖集， $\overline{\m{VC}}$ 为一个 $\m G$ 的独立集

实际上这两者都等价于证明 $\m {IS}$ 中没有连边，这是显然的

因此，如果我们记 $|\m{IS}|$ 为 $\m G$ 中最大独立集的大小，$|\m{VC}|$ 为 $\m G$ 中最小覆盖集的大小，那么由上可知 $|\m{IS}|+|\m{VC}|=|\m V|$

IV. Konig 定理

在一般图上求解最小覆盖集和最大独立集都是 NP - Completed 的，但在二分图上 $\m{VC}$（最小覆盖集）有很好的性质：

记 $\m M$ 为 $\m G$ 的最大匹配，那么 $|\m {VC}|=|\m M|$

V. 证明

考虑把 $|\m{VC}|=|\m M|$ 拆分成 $|\m {VC}|\ge |\m M|$ 和 $|\m{VC}|\le |\m M|$ 两个命题即可

注意到 $|\m {VC}|\ge|\m M|$ 是显然的，因为 $\m M$ 中的每一条边都至少有一个端点在 $\m {VC}$ 中，又因为 $\m M$ 的边没有公共端点，我们可以得到 $|\m M|\le|\m {VC}|$

接下来证明 $|\m{VC}|\le|\m M|$，事实上，我们只需要找到一个覆盖集 $\m {VC'}$ 满足 $|\m{VC'}|=|\m M|$ 就可以得出结论 $|\m{VC}|\le|\m{VC'}|=|\m M|$

类似 Hall 定理的证明过程，我们把 $\m V$ 划分成 $\m{S_X},\m{T_X},\m{S_Y},\m{T_Y}$ 四个点集

由 Hall 定理的引理一，我们能够知道不存在连接 $\m{S_X}$ 和 $\m{T_Y}$ 的边，因此 $\m{T_X}\cup\m{S_Y}$ 一定是一个覆盖集，我们只需要证明 $|\m{T_X}|+|\m{S_Y}|=|\m M|$ 即可

事实上，我们首先可以证明 $\m M$ 中没有连接 $\m{T_X}$ 和 $\m{S_Y}$ 的边，这个东西的证明和之前的过程大致相同，只需要注意 $\m{S_Y}$ 通过某条 $\m M$ 中的边一定会把连接到的点生成到 $\m{S_X}$ 里面去即可

然后我们只需要证明 $\m M$ 中的每条边恰好连接 $\m{S_Y}\cup\m{T_X}$ 中的一个顶点，证明和上面的依然类似，考虑 $\m{S_Y},\m{T_X}$ 的生成过程：

由于图上没有增广路，所以 $\m{S_Y}$ 一定会和某个 $\m{S_X}$ 中的点通过 $\m M$ 中的边相连
由于 $\m{T_X}$ 里的点才不会在初始状态下被加入 $\m{S_X}$，因此每个 $\m{T_X}$ 中的点必须有一条 $\m{M}$ 中的边连接

综上所述，我们能够得到一个大小为 $|\m M|$ 的覆盖集 $\m {T_X}\cup\m{S_Y}$

联立两式有 $|\m{VC}|=|\m M|$，故原命题得证

事实上，以上的证明过程告诉了我们如何求解一个二分图 $\m G$ 的某个最小覆盖集和最大独立集

五、最小路径覆盖

I. 定义

在 DAG $\m G=(\m V,\m E)$ 上选择若干条简单路径构成的集合 $\m P$，使得 $\m V$ 中的每一个顶点都恰好在 $\m P$ 中的一条简单路径上

则 $\m P$ 为 $\m G$ 的一个路径覆盖

注意：这里的简单路径的长度可能为 $0$

II. 求解

构造一个二分图 $\m G'=({\m X,\m Y,\m {E'}})$，其中 $\m{E'}=\left\{(x_i,y_j)\mid(i,j)\in\m E\right\}$

此时对于一个 $\m{G'}$ 的匹配 $\m M$，我们将所有 $\m M$ 中的边 $e'$ 对应回 $\m G$ 上，得到一个路径集合 $\m P$

因为 $\m M$ 是一个 $\m {G'}$ 的匹配，我们可以发现 $\m P$ 中没有两条边有相同的起点或终点，每个点至多各有一条边以其为起点和终点，那么这两条边可以连成一条路径

综上，我们得到一个 $\m{G'}$ 中的匹配和 $\m G$ 中的路径覆盖的双射，且满足 $|\m P|=|\m V|-|\m M|$

如果我们记 $\m G$ 中的最小路径覆盖的大小为 $|\m P|$，$\m{G'}$ 中的最大匹配大小为 $|\m M|$，那么我们有 $|\m P|=|\m V|-|\m M|$

六、习题演练

I. [CF Gym 101915D] - Largest Group

$\text{Link}$

思路分析

对每个男生认识的点状压，然后枚举每个男生构成的集合，取他们认识的女生集合的交，然后更新答案即可

时间复杂度 $\Theta(p2^p)$

代码呈现

#include<bits/stdc++.h>
using namespace std;
const int MAXN=20;
int f[MAXN];
inline int calc(int S) { return __builtin_popcount(S); }
inline int bit(int k) { return 1<<k; }
inline void solve() {
	int n,m,ret=0;
	memset(f,0,sizeof(f));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		--u,--v;
		f[u]|=bit(v);
	}
	for(int S=1;S<bit(n);++S) {
		int T=bit(n)-1;
		for(int i=0;i<n;++i) if(S&bit(i)) T&=f[i];
		ret=max(ret,calc(S)+calc(T));
	}
	printf("%d\n",ret);
}
signed main() {
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

II. [ACWing380] - 骑士放置

$\text{Link}$

思路分析

对棋盘进行黑白染色，注意到一个骑士能够攻击到的所有格子都和其本身所在格子异色，故将两个能互相攻击的格子连边，构造二分图

原问题转化为求二分图上的最大独立集，求出最大匹配即可

时间复杂度 $\Theta(n^2m^2)$

代码呈现

#include<bits/stdc++.h> 
using namespace std;
const int MAXN=101,MAXS=1e4+1;
bool a[MAXN][MAXN],vis[MAXS];
int n,m,tar[MAXS];
vector <int> edge[MAXS];
int dx[]={1,1,-1,-1,2,2,-2,-2};
int dy[]={2,-2,2,-2,1,-1,1,-1};
inline int id(int x,int y) {
	if(x<1||x>n||y<1||y>m||a[x][y]) return -1;
	return (x-1)*m+y;
}
inline bool match(int p) {
	for(int x:edge[p]) {
		if(vis[x]) continue;
		vis[x]=true;
		if(tar[x]==-1||match(tar[x])) {
			tar[x]=p;
			return true;
		}
	}
	return false;
}
signed main() {
	int t,ans=0;
	scanf("%d%d%d",&n,&m,&t);
	for(int i=1;i<=t;++i) {
		int x,y;
		scanf("%d%d",&x,&y);
		a[x][y]=true;
	}
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			if((i+j)%2==1||id(i,j)==-1) continue;
			for(int k=0;k<8;++k) {
				int x=i+dx[k],y=j+dy[k];
				if(id(x,y)==-1) continue;
				edge[id(i,j)].push_back(id(x,y));
			}
		}
	}
	memset(tar,-1,sizeof(tar));
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=m;++j) {
			if((i+j)%2==1||id(i,j)==-1) continue;
			memset(vis,false,sizeof(vis));
			if(match(id(i,j))) ++ans;
		}
	}
	printf("%d\n",n*m-t-ans);
	return 0;
}

III. [POJ1422] - Air Raid

$\text{Link}$

思路分析

最小路径覆盖的模板题，跑一边二分图最大匹配即可

时间复杂度 $\Theta(nm)$

代码呈现

#include<stdio.h>
#include<vector>
#include<string.h> 
using namespace std;
const int MAXN=121;
vector <int> edge[MAXN];
bool vis[MAXN];
int tar[MAXN];
inline bool match(int p) {
	for(int i=0;i<(int)(edge[p].size());++i) {
		int x=edge[p][i];
		if(vis[x]) continue;
		vis[x]=true;
		if(tar[x]==-1||match(tar[x])) {
			tar[x]=p;
			return true;
		}
	}
	return false;
}
inline void solve() {
	int n,m;
	scanf("%d%d",&n,&m);
	memset(tar,-1,sizeof(tar));
	for(int i=1;i<=n;++i) edge[i].clear();
	for(int i=1;i<=m;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		edge[u].push_back(v);
	}
	int ret=n;
	for(int i=1;i<=n;++i) {
		memset(vis,false,sizeof(vis));
		if(match(i)) --ret;
	}
	printf("%d\n",ret);
	return ;
}
signed main() {
	int T;
	scanf("%d",&T);
	while(T--) solve();
	return 0;
}

IV. [POJ1548] - Robots

$\text{Link}$

思路分析

考虑对于两个点 $p_i:(x_i,y_i)$ 和 $p_j:(x_j,y_j)$，如果可以从 $p_i$ 走到 $p_j$，即 $x_i\le x_j,y_i\le y_j$，那么就在图 $\m G$ 上连一条有向边 $i\to j$，然后求出 $\m G$ 的最小路径覆盖即可

设 $n$ 为点的数量，时间复杂度 $\Theta(n^3)$

代码呈现

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
const int MAXN=1001;
int x[MAXN],y[MAXN],tar[MAXN],n;
vector <int> edge[MAXN];
bool vis[MAXN];
inline bool match(int p) {
	for(int i=0;i<(int)(edge[p].size());++i) {
		int x=edge[p][i];
		if(vis[x]) continue;
		vis[x]=true;
		if(tar[x]==-1||match(tar[x])) {
			tar[x]=p;
			return true;
		}
	}
	return false;
}
inline void solve() {
	for(int i=1;i<=n;++i) edge[i].clear();
	int ret=n;
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			if(i!=j&&x[i]<=x[j]&&y[i]<=y[j]) {
				edge[i].push_back(j);
			}
		}
	}
	memset(tar,-1,sizeof(tar));
	for(int i=1;i<=n;++i) {
		memset(vis,false,sizeof(vis));
		if(match(i)) --ret;
	}
	printf("%d\n",ret);
}
signed main() {
	int a,b;
	n=0;
	while(true) {
		scanf("%d%d",&a,&b);
		if(a==-1&&b==-1) break;
		else if(a==0&&b==0) {
			solve();
			n=0;
		} else {
			++n;
			x[n]=a,y[n]=b;
		}
	}
	return 0;
}

V. [POJ3216] - Repairing Company

$\text{Link}$

思路分析

考虑建立图 $\m{G'}=(\m{V'},\m{E'})$，$\m {V'}$ 是所有的任务

对于每一个修理任务建成一个点 $i\to j$ 当且仅当第 $i$ 个任务完成后可以去完成 $j$

考虑 Floyd 处理出全源最短路 $\Delta_{i,j}$ 表示 $i,j$ 之间的最短路

那么：$(i,j)\in \m E'\iff t_i+d_i+\Delta_{p_i,p_j}\le p_j$

因此建出 $\m{G'}$ 后求出其最小路径覆盖即可得到答案

时间复杂度 $\Theta(n^3+m^3)$

代码呈现

#include<stdio.h>
#include<vector>
#include<string.h>
using namespace std;
const int MAXM=201,MAXN=21,INF=1e9;
int dis[MAXN][MAXN];
int p[MAXM],t[MAXM],d[MAXM],n,m;
vector <int> edge[MAXM];
bool vis[MAXM];
int tar[MAXM];
inline bool match(int p) {
	for(int i=0;i<(int)(edge[p].size());++i) {
		int x=edge[p][i];
		if(vis[x]) continue;
		vis[x]=true;
		if(tar[x]==-1||match(tar[x])) {
			tar[x]=p;
			return true;
		}
	}
	return false;
}
inline void solve() {
	for(int i=1;i<=m;++i) edge[i].clear();
	memset(tar,-1,sizeof(tar));
	for(int i=1;i<=n;++i) {
		for(int j=1;j<=n;++j) {
			scanf("%d",&dis[i][j]);
			if(dis[i][j]==-1) dis[i][j]=INF;
		}
	}
	for(int k=1;k<=n;++k) {
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
			}
		}
	}
	for(int i=1;i<=m;++i) scanf("%d%d%d",&p[i],&t[i],&d[i]);
	for(int i=1;i<=m;++i) {
		for(int j=1;j<=m;++j) {
			if(t[i]+d[i]+dis[p[i]][p[j]]<=t[j]) edge[i].push_back(j);
		}
	}
	int ret=m;
	for(int i=1;i<=m;++i) {
		memset(vis,false,sizeof(vis));
		if(match(i)) --ret;
	}
	printf("%d\n",ret);
} 
signed main() {
	while(true) {
		scanf("%d%d",&n,&m);
		if(n==0&&m==0) break;
		solve();
	}
	return 0;
}

VI. [POJ2594] - Treasure Exploration

$\text{Link}$

思路分析

求可相交路径最小覆盖问题，考虑转化为普通的最小路径覆盖问题

考虑建立图 $\m{G'}=(\m V,\m{E'})$，其中 $(i,j)\in \m{E'}$ 等价于在原图中可以从 $i$ 走到 $j$

此时 $\m {G'}$ 中的一条边 $u\to v$ 也对应 $\m G$ 中的一条 $u\to v$ 的路径，可以证明 $\m{G'}$ 中的一个普通最小路径覆盖 $\m{P'}$ 和 $\m G$ 中的一个可相交路径最小覆盖 $\m P$ 是一一对应的，证明如下：

证：

注意到 $\m{G'}$ 中的一个普通路径覆盖一定覆盖了 $\m V$，所以每个 $\m {P'}$ 在 $\m G$ 上都会成为一个合法的 $\m P$

对于一个 $\m G$ 中的可相交路径最小覆盖，可以考虑成若干条路径 $p_{u_i}\to p_{v_i}$，那么显然每条这样的路径都可以在 $\m {G'}$ 中找到一条边 $p_{u_i}\to p_{v_i}$ 与之对应，注意到因为 $p_{u_i}\to p_{v_i}$ 是一条独立的路径，所以不存在 $j$ 使得 $p_{v_j}=p_{u_i}$ 或者 $p_{v_i}=p_{u_j}$，因此这样的路径对应到 $\m{P'}$ 上一定是一个普通路径路径覆盖的一部分，因为不存在另外一条 $\m{P'}$ 中的边与 $p_{u_i}$ 或者 $p_{v_i}$ 相交

综上所述，我们证明了 $\m{P}$ 和 $\m {P'}$ 之间存在双射关系

此时我们只需要在 $\m{G'}$ 中求出最小路径覆盖的的大小即可，注意到 $\m{G'}$ 的建立事实上只要用 Floyd 传递闭包，因此最终的时间复杂度是 $\Theta(n^3)$

代码呈现

#include<stdio.h>
#include<string.h>
const int MAXN=501;
bool link[MAXN][MAXN],vis[MAXN];
int tar[MAXN],n,m;
inline bool match(int p) {
	for(int x=1;x<=n;++x) {
		if(!link[p][x]||x==p||vis[x]) continue;
		vis[x]=true;
		if(tar[x]==-1||match(tar[x])) {
			tar[x]=p;
			return true;
		}
	}
	return false;
}
inline void solve() {
	memset(link,false,sizeof(link));
	memset(tar,-1,sizeof(tar));
	for(int i=1;i<=n;++i) link[i][i]=true;
	for(int i=1;i<=m;++i) {
		int u,v;
		scanf("%d%d",&u,&v);
		link[u][v]=true;
	}
	for(int k=1;k<=n;++k) {
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				link[i][j]|=link[i][k]&link[k][j];
			}
		}
	}
	int ret=n;
	for(int i=1;i<=n;++i) {
		memset(vis,false,sizeof(vis));
		if(match(i)) --ret;
	}
	printf("%d\n",ret);
}
signed main() {
	while(true) {
		scanf("%d%d",&n,&m);
		if(n==0&&m==0) break;
		solve();
	}
	return 0;
}