二分图（一）
\(\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. 习题演练
考虑对于原本的棋盘做黑白间隔染色，那么每个骨牌一定覆盖两个相邻的异色格子，因此把黑白色的格子分别看成左部点和右部点，相邻的格子连边，可以变成一张二分图
然后只需要跑一遍二分图最大匹配，选择的边对应为覆盖其两个顶点的一个骨牌，只需要判断是否覆盖满了即可
注意到做法自动带匹配方案，因此输出很简单
代码如下：
#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\or 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
思路分析
对每个男生认识的点状压，然后枚举每个男生构成的集合，取他们认识的女生集合的交，然后更新答案即可
时间复杂度 \(\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] - 骑士放置
思路分析
对棋盘进行黑白染色，注意到一个骑士能够攻击到的所有格子都和其本身所在格子异色，故将两个能互相攻击的格子连边，构造二分图
原问题转化为求二分图上的最大独立集，求出最大匹配即可
时间复杂度 \(\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
思路分析
最小路径覆盖的模板题，跑一边二分图最大匹配即可
时间复杂度 \(\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
思路分析
考虑对于两个点 \(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
思路分析
考虑建立图 \(\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
思路分析
求可相交路径最小覆盖问题，考虑转化为普通的最小路径覆盖问题
考虑建立图 \(\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;
}
VII. 扑克牌（证明题）
命题
将一副扑克牌分成 \(13\) 堆，每一堆中恰好 \(4\) 张牌
求证：我们总是可以从每堆里面选出一张来使得选出的排构成 \(\texttt A,\texttt2,\texttt3,\cdots,\texttt{10},\texttt J,\texttt Q,\texttt K\)
证明
考虑将这些堆编号为 \(H_1\sim H_{13}\)，扑克牌数字记为 \(1\sim 13\)
构造一张二分图 \(\m{G}=(\m X,\m Y,\m E)\)，其中 \(\m X=\{H_1,H_2,\cdots,H_{13}\},\m Y=\{1,2,\cdots 13\}\)， \((x_i,y_j)\in \m E\iff j\in H_i\)
即每个堆向其有的所有数字连边，此时我们即证明 \(\m G\) 中有大小为 \(|\m X|\) 的匹配
注意到对于 \(k\) 个数字，至少需要 \(k\) 个牌堆才能装下这些牌，即 \(\forall \m A\in\m Y:|N(\m A)|\le |\m A|\)，运用 Hall 定理可以证明 \(\m G\) 中存在完美匹配
故原命题得证
VIII. Periodic Scheduling（证明题）
命题
假设有 \(n\) 种任务，你每天至多可以执行一种任务（也可以不执行）
第 \(i\) 种任务有一个参数 \(t_i\)， 表示 \(\forall x\in \Z^+\)，在区间 \((x\times t_i, (x+1)\times t_i]\) 这些天你必须执行任务 \(i\) 至少一次
令 \(L = \operatorname{lcm}(t_1,...,t_n)\)，求证：存在一个可行的任务安排方案，当且仅当 \(\sum_{i=1}^n \dfrac L{t_i}\le L\)
证明
构造二分图 \(\m G=(\m X,\m Y,\m E)\)
\(\m X\) 表示每个任务的每个执行区间，即 \(x_{i,j}\) 表示 \((j\times t_i,(j+1)\times t_i]\)，\(\m Y\) 表示第 \(1\sim L\) 的日期 \(y_1\sim y_L\)
\((x_{i,j},y_k)\in\m E\iff k\in(j\times t_i,(j+1)\times t_i]\) ，即向其需要的区间连边
此时一种合法的任务安排方案等价于 \(\m G\) 中有一个大小为 \(|\m X|\) 的匹配
运用 Hall 定理得到其一个必要条件是 \(|\m X|\le|\m Y|\) 即 \(\sum_{i=1}^n \dfrac L{t_i}\le L\)，故必要性得证
下证充分性：
运用 Hall 定理，原命题等价为 \(|\m X|\le |\m Y|\implies\forall\m A\subseteq \m X:|N(\m A)|\ge|\m A|\)
考虑构造函数 \(f(\m A)=|N(\m A)|-|\m A|\)，原命题再化为 \(f(\m X)\ge 0\implies \forall \m A\subseteq \m X:f(\m A)\ge 0\)
再转化成 \(\forall \m A\subseteq\m X,f(\m A)\ge f(\m X)\)
采用数学归纳法，令任务数为 \(k\)，对于 \(k=1\) 时显然成立
假设对于 \(k=n-1\) 时成立，令 \(\m X_n=\{x_{n,1},x_{n,2},\cdots,x_{n,\frac{L}{t_n}}\}\)，即所有对应任务 \(n\) 的左部点构成的集合
那么我们假设此时 \(\m A\cup\m X_n=\m{A}_n\)，而 \(\overline{\m X_n}=\m{X'},\overline{\m A_n}=\m{A'}\)
根据归纳法假设， \(\forall \m{A'}:f(\m A')\ge f(\m {X'})\)
注意到 \(f(\m X)= f(\m{X'})-\dfrac L{t_n}=f(\m{X'})-|\m X_n|\)，\(f(\m A)\ge f(\m A')-|\m A_n|\)
因此 \(f(\m A)-f(\m X)=(f(\m {A'})-f(\m{X'}))+(|\m X_n|-|\m A_n|)\ge 0\)，故此时对于 \(k=n\) 也成立
事实上，当且仅当 \(\m A=\m X\) 的时候才有 $f(\m A)=f(\m X ) $
综上所述，原命题得证
标签：二分,VC,匹配,int,路径,MAXN From： https://www.cnblogs.com/DaiRuiChen007/p/17026182.html