二分图（二）
\(\newcommand \m \mathbf\)
\(\text{By DaiRuiChen007}\)
一、匹配与博弈
I. 博弈规则
Undirected Vertex Geography（简称UVG）游戏规则如下：
在一张二分图 \(\m G=(\m X,\m Y,\m E)\) 上有一个棋子在节点 \(v\) 上，\(v\in\m X\)：
两名玩家轮流将这枚棋子挪到某个 \(v\) 之相邻的节点 \(v'\) 上，如果某一方不能移动，则立刻判负，请问谁有必胜策略
II. 结论
记 \(\m M\) 为某个 \(\m G\) 的最大匹配，先手胜利当且仅当不存在 \(\m M\) 使得 \(v\not\in V(\m M)\)
III. 证明
先证必要性：
证：
由假设得 \(\forall \m M:v\in V(\m M)\)
我们为先手设计一个移动策略：即每次都沿着 \(\m M\) 中的边移动
现在我们需要证明当到达某个 \(x_i\) 后，一定存在一条边 \((x_i,y_j)\in\m M\)
考虑反证法，若当前到达 \(x_i\) 后 \(\m M\) 中没有相邻的匹配边，假设当前的移动路径为 \(\m A\)，显然 \(\m A\) 是 \(\m M\) 的一条交错轨
我们构造一个新的边集 \(\m{M'}=\m M\oplus \m A\)，可以证明 \(\m{M'}\) 依然是 \(\m G\) 的一个匹配，且满足 \(|\m{M'}|=|\m M|\)，\(v\not\in V(\m{M'})\)
与原命题矛盾，故假设不成立，故原命题得证
再证充分性：
现将原命题转化为其逆否命题：如果存在一个 \(\m G\) 的最大匹配 \(\m M\) 满足 \(v\not\in V(\m M)\)，则后手一定有一个必胜策略：
证：
可以推知：\(\forall (v,v')\in \m E:v'\in\m{M}\)，否则 \((v,v')\) 也可以加入 \(\m M\) 中，与 \(\m M\) 是最大匹配矛盾
因此先手一定会把棋子移动到 \(\m M\) 中的某个顶点上
类似上面的证明：我们为后手设计一个移动策略：即每次都沿着 \(\m M\) 中的边移动
同上，原命题可以看做：证明当到达某个 \(y_i\) 后，一定存在一条边 \((x_j,y_i)\in\m M\)
同样反证法，设 \(y_i\) 没有 \(\m M\) 中的匹配边与其相连，则当前移动的路径 \(\m A\) 会形成一个增广轨，这与 \(\m M\) 是 \(\m G\) 的一个最大匹配同样矛盾，故原命题得证
综上所述，当且仅当不存在最大匹配 \(\m M\) 使得 \(v\not\in V(\m M)\) 时，先手有必胜策略
IV. 算法实现
求解 UVG 问题，只需要判断某个点是否一定会在 \(\m G\) 的最大匹配中
下面的伪代码给出了在 \(\Theta(nm)\) 复杂度内计算所有先手必胜点的策略
同理，我们可以考虑计算某条边是否一定会在 \(\m G\) 的最大匹配中，时间复杂度 \(\Theta(m^2)\)
二. HK 算法
I. 主要思想
HK 算法（Hopcroft-Karp 算法）是增广轨算法的一种优化
我们每次尽可能多地寻找不相交的、长度最短的增广路
注意这里的尽可能多是指不存在其他满足条件的路径，而不是让选择的路径数量达到最大值
可以理解为一个局部上的最优解，而非全局上的最优解
假如存在一种 \(\Theta(m)\) 复杂度的方式求解这样的增广轨集，可以证明这样的增广次数是不超过 \(\Theta(\sqrt n)\) 次的，所以最终的复杂度是 \(\Theta(m\sqrt n)\) 的
II. 复杂度分析
首先，我们需要证明一个引理：
引理：假设第 \(k\) 轮增广的增广路长度为 \(l_k\)，则 \(\{l_k\}\) 严格递增
证明：
假设当前得到的匹配为 \(\m M\)，然后我们在接下来的一轮增广到了增广轨 \(\m P_1\sim\m P_k\)，长度为 \(l\)，然后我们得到一个新匹配 \(\m {M'}\)，在 \(\m{M'}\) 上得到的了一条增广轨 \(\m{P'}\)，即证 \(l<|\m {P'}|\)
如果 \(\m {P'}\) 与所有 \(\m P\) 都不相交，那么如果 \(l\ge |\m{P'}|\) 那么上一轮一定会找到增广轨 \(\m{P'}\)，矛盾，此时原命题得证
因此需要考虑 \(\m{P'}\) 与某个 \(\m P\) 相交的情况
考虑一个边集 \(\m Q=\m{P'}\oplus\m P_1\oplus\m P_2\oplus\cdots\oplus \m{P}_k\)
由于 \(\m P'\) 中至少有一条重边，因此 \(|\m Q|\le k\times l+|\m{P'}|-2\)
我们称某个匹配 \(\m M\) 的 Free-Point 为不与 \(\m M\) 中的边相连的点
显然 \(\m P_1\sim\m P_k,\m{P'}\) 的起终点都是 Free-Point，可以证明这些 Free-Point 都是互不相同的
因此 \(\m Q\) 中至少有 \(2(k+1)\) 个 Free-Point
当然，我们可以知道这些 Free-Point 之间都会通过 \(\m Q\) 中某些 \(\m M\) 的交错轨相连，因此 \(\m Q\) 中至少有 \((k+1)\) 条增广轨
由于 \(l\) 是增广轨长度的最小值，我们得到：\(|\m Q|\ge l\times (k+1)\)
两边联立，有 \(|\m P'|\ge l+2\)
原命题得证
接下来，我们证明：假设在 \(\sqrt n\) 轮增广以后，没有得到最大匹配，则至多再进行 \(\sqrt n\) 轮增广
证明如下：
假设此时的匹配为 \(\m M\)，最大匹配为 \(\m{M^\star}\)，考察 \(\m Q=\m M\oplus\m{M^\star}\)：
显然 \(\m Q\) 中只有偶环和若干条不相交的交错轨 \(\m A\)
这些交错轨中的增广轨即为接下来增广的目标
由于已经进行了 \(\sqrt n\) 轮增广，运用引理可得 \(|\m A|\ge \sqrt n\)
又因这些交错轨互不相交，所以剩下的交错轨的数量 \(\le\dfrac n{\sqrt n}=\sqrt n\)
因此还需要进行不超过 \(\sqrt n\) 轮增广
故 HK 算法的时间复杂度为 \(\Theta(m\sqrt n)\)
III. 算法实现
受 Dinic 算法优化 EK 算法这一过程的启发，我们同样考虑通过分层图来快速求出所有最短的增广路
考虑在我们朴素通过 BFS 求出所有可能成为增广轨终点的集合 \(\m S\) 的过程中，记录每个点被搜到的 BFS 序（只有左到右才让深度 \(+1\)），这一步的伪代码如下：
接下来，我们在分层图上 DFS，每次深搜只搜深度的差为 \(1\) 的点，将左部点中所有的 Free-Point 都考虑一次，注意每一次整体增广的过程中都不需要重复访问节点，因此我们得出这一步的伪代码：
IV. 习题演练一
CodeForces1423B - Valuable Paper
首先二分最大权值，然后用 HK 算法求出最大匹配即可
时间复杂度 \(\Theta(n\log w\sqrt m)\)，\(w\) 为边权
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+1,INF=1e9;
struct node {
int des,val;
};
vector <node> edge[MAXN];
int tar[MAXN],dep[MAXN],n,m;
bool vis[MAXN];
inline bool left(int p) { return p<=n; }
inline bool right(int p) { return p>n; }
inline void BFS(int thershold) {
memset(dep,0x3f,sizeof(dep));
queue <int> S;
for(int i=1;i<=n;++i) {
for(auto e:edge[i]) {
if(e.val>thershold) continue;
if(tar[e.des]==i) goto nxt;
}
dep[i]=0;
S.push(i);
nxt:;
}
while(!S.empty()) {
int p=S.front();
S.pop();
int nxt_dep=left(p)?dep[p]+1:dep[p];
for(auto e:edge[p]) {
if(e.val>thershold) continue;
int x=e.des;
if(left(p)&&tar[x]==p) continue;
if(right(p)&&tar[p]!=x) continue;
if(dep[x]>=INF) {
dep[x]=nxt_dep;
S.push(x);
}
}
}
}
inline bool dfs(int p,int thershold) {
if(vis[p]) return false;
vis[p]=true;
for(auto e:edge[p]) {
if(e.val>thershold) continue;
int x=e.des;
if(vis[x]||dep[x]!=dep[p]+1) continue;
vis[x]=true;
if(tar[x]==-1||dfs(tar[x],thershold)) {
tar[x]=p;
return true;
}
}
return false;
}
inline int MaxMatching(int thershold) {
memset(tar,-1,sizeof(tar));
int ret=0;
while(true) {
BFS(thershold);
bool ok=false;
memset(vis,false,sizeof(vis));
for(int i=1;i<=n;++i) {
if(!dep[i]&&!vis[i]) {
if(dfs(i,thershold)) {
ok=true;
++ret;
}
}
}
if(!ok) break;
}
return ret;
}
signed main() {
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i) {
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
v+=n;
edge[u].push_back((node){v,w});
edge[v].push_back((node){u,w});
}
int l=0,r=INF,res=-1;
while(l<=r) {
int mid=(l+r)>>1;
if(MaxMatching(mid)==n) r=mid-1,res=mid;
else l=mid+1;
}
printf("%d\n",res);
return 0;
}
V. 习题演练二
首先考虑建立二分图 \(\m G=(\m X,\m Y,\m E)\)
其中 \(\m X\) 表示每个人，\(\m Y\) 表示每个门在某个时刻的状态（拆若干个点），\(\m E\) 中连接 \((x_i,y_{j,t})\) 表示第 \(i\) 个人能在第 \(t\) 个时刻或之前到达第 \(j\) 扇门处，\(\m E\) 可以通过对于每扇门作 BFS 预处理距离得到
可以二分 \(t\)，如果此时最大匹配 \(\m M\) 满足 \(|\m M|=|\m X|\) 则成立
但是也有不二分的做法：
由于从 \(t\to t+1\) 的过程，只会增加若干个右部点，我们其实只需要在处理完这些右部点的连边情况后，在新的图 \(\m {G'}\) 上寻找一条以当前节点为顶点的增广轨即可，如果存在则最大匹配的大小加一
时间复杂度 \(\Theta((nm)^3)\)
代码如下：
#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#define pii pair<int,int>
using namespace std;
const int MAXN=15,MAXS=201,MAXP=3e4+1;
char ch[MAXN][MAXN];
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
int dis[MAXS][MAXS],n,m;
bool vis[MAXS];
int tar[MAXS];
vector <int> edge[MAXP];
inline int id(int i,int j) {
if(i<1||i>n||j<1||j>m||ch[i][j]=='X') return -1;
return (i-1)*m+j;
}
inline void BFS(int sx,int sy) {
queue <pii> q;
dis[id(sx,sy)][id(sx,sy)]=0;
q.push(make_pair(sx,sy));
while(!q.empty()) {
int px=q.front().first,py=q.front().second;
q.pop();
for(int k=0;k<4;++k) {
int tx=px+dx[k],ty=py+dy[k];
if(id(tx,ty)==-1||ch[tx][ty]=='D'||dis[id(sx,sy)][id(tx,ty)]!=-1) continue;
dis[id(sx,sy)][id(tx,ty)]=dis[id(sx,sy)][id(px,py)]+1;
q.push(make_pair(tx,ty));
}
}
}
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() {
cin>>n>>m;
memset(tar,-1,sizeof(tar));
memset(dis,-1,sizeof(dis));
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
cin>>ch[i][j];
}
}
vector <int> src;
int tot=0,ret=0;
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
if(ch[i][j]=='D') {
src.push_back(id(i,j));
BFS(i,j);
} else if(ch[i][j]=='.') ++ret;
}
}
for(int T=0;T<=n*m;++T) {
for(int i=0;i<(int)src.size();++i) {
int x=src[i];
edge[++tot].clear();
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
if(ch[i][j]=='.'&&dis[x][id(i,j)]!=-1&&dis[x][id(i,j)]<=T) {
edge[tot].push_back(id(i,j));
}
}
}
memset(vis,false,sizeof(vis));
if(match(tot)) --ret;
if(ret==0) {
cout<<T<<'\n';
return ;
}
}
}
cout<<"impossible\n";
}
signed main() {
int T;
cin>>T;
while(T--) solve();
return 0;
}
三、特殊图的匹配问题
I. 习题演练一
考虑将每个攻击连接边 \((a_i,b_i)\)，那么一次攻击等价于删掉这条边和其某个端点，问能够有一种策略使得所有 \(1\sim k\) 的点都被删除
显然，在一个连通块 \(\m {G'}=(\m{V'},\m{E'})\) 中，这样做成立的一个充分条件是 \(|\m{E'}|\ge|\m{V'}|\)，事实上对于所有这样的 \(\m {G'}\)，我们可以求出其中的一个生成树，然后将其中某一个连接了至少一条非树边 \(e\) 的点 \(r\) 作为树根，将树上的每个点和它的父边删除，然后把 \(r\) 和 \(e\) 删除，因此 \(|\m {E'}|\ge|\m {V'}|\) 是 \(\m{G'}\) 可以完全删除的一个充分必要条件
因此我们用并查集维护动态加边即可，时间复杂度 \(\Theta(n\log m)\)，\(m\) 为 \(a_i,b_i\) 的值域
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e4+1;
int dsu[MAXN],edgeSize[MAXN],nodeSize[MAXN];
vector <int> edge[MAXN];
inline int find(int x) {
if(x==dsu[x]) return x;
return dsu[x]=find(dsu[x]);
}
signed main() {
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
for(int i=1;i<MAXN;++i) {
dsu[i]=i;
nodeSize[i]=1;
for(int x:edge[i]) {
if(x>i) {
++edgeSize[find(i)];
continue;
}
int u=find(x),v=find(i);
if(u!=v) dsu[u]=v,nodeSize[v]+=nodeSize[u],edgeSize[v]+=edgeSize[u];
else ++edgeSize[v];
}
int f=find(i);
if(nodeSize[f]>edgeSize[f]) {
printf("%d\n",i-1);
return 0;
}
}
puts("10000");
return 0;
}
II. 习题演练二
我们把合法的 \((i,j)\) 连起来得到一张图 \(\m G\)，原问题转化为在 \(\m G\) 中求一个最大匹配
普通图上的最大匹配有一个性质：如果存在某条边 \((u,v)\) 使得 \(\operatorname{deg}(u)=1\)，那么 \((u,v)\) 肯定会在某个最大匹配中
证明如下：
证：
假设 \(\m M\) 是 \(\m G\) 的某个最大匹配，且 \((u,v)\not\exists\m M\)
- \(v\not\in V(\m M)\)
令 \(\m {M'}=\m M+(u,v)\)，能够证明 \(\m{M'}\) 也是一个匹配，且 \(|\m{M'}|>|\m M|\)，与 \(\m M\) 是最大匹配矛盾，舍
- \(v\in V(\m M)\)
设 \((v,u')\in\m M\)，令 \(\m{M'}=\m M-(v,u')+(u,v)\)，同样 \(\m{M'}\) 是一个大小为 \(|\m M|\) 的匹配，同样是 \(\m G\) 的一个最大匹配
综上，一定有至少一个最大匹配包含边 \((u,v)\)
对于这道题也是一样的，如果某个 \(a_i\) 只有某一个值（不是元素）\(a_j\) 使得 \(a_i+a_j\) 满足要求，那么显然可以先选 \((i,j)\)
考虑一个贪心的解法：每次选取的 \((a_i,a_j)\) 最大化 \(k\)，即每次选择的 \(a_i+a_j\) 都是所有合法对里的最大值，我们要证明，如果 \(a_i\ge a_j\)，那么合法的 \(a_j\) 的值对于 \(a_i\) 来说是唯一的
证：
采用反证法，设存在 \(a_{j'}\) 使得 \(a_i+a_{j'}=2^{k'}\)，\(k'\) 为自然数
由于 \(k\) 是所有可行解里的最大值，那么 \(k'<k\)
注意到：由于 \(a_i\ge a_j\)，有 \(a_i\ge 2^{k-1}\)
所以 \(a_{j'}=2^{k'}-a_\le<2^{k-1}-a_i\le 0\)
与 \(a_{j'}\in \mathbb Z^+\) 矛盾，舍
故原命题得证
具体实现可以从大到小枚举 \(k\)，然后用双指针或者 set 扫一遍
时间复杂度 \(\Theta(nk)\) 或 \(\Theta(nk\log n)\)，\(k=\log a_i\)
代码如下
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+1;
inline int bit(int k) { return 1<<k; }
int a[MAXN];
multiset <int> S;
signed main() {
int n,res=0;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
scanf("%d",&a[i]);
S.insert(a[i]);
}
sort(a+1,a+n+1);
for(int k=30;k>=1;--k) {
for(int i=1;i<=n;++i) {
if(a[i]>bit(k-1)) break;
auto x=S.lower_bound(a[i]);
if(x==S.end()||*x!=a[i]) continue;
auto y=S.upper_bound(bit(k)-a[i]);
--y;
if(x!=y&&(*x+*y==bit(k))) {
S.erase(x);
S.erase(y);
++res;
}
}
}
printf("%d\n",res);
return 0;
}
四、习题演练
I. [洛谷1129] - 矩阵游戏
思路分析
考虑建立二分图 \(\m G=(\m X,\m Y,\m E)\)，其中 \(\m X\) 表示棋盘的行 \(R_1\sim R_n\)，\(\m Y\) 表示棋盘的列 \(C_1\sim C_n\)，\((R_i,C_j)\in\m E\) 当且仅当 \(a_{i,j}\) 是黑色的
那么此时如果存在一个 \(\m G\) 的完美匹配 \(\m M=\{(R_1,C_{m_1}),(R_2,C_{m_2}),\cdots,(R_n,C_{m_n})\}\)，那么我们可以通过对列进行排列使得列的排列 \(\{1,2,\cdots,n\}\) 变成 \(\{m_1,m_2,\cdots,m_n\}\)，此时主对角线的格子都是黑色的
可以证明这个条件是必要的，所以只需要在 \(\m G\) 中求出最大匹配
时间复杂度 \(\Theta(n^3)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=201;
vector <int> edge[MAXN];
int tar[MAXN];
bool vis[MAXN];
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 solve() {
memset(tar,-1,sizeof(tar));
int n;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
edge[i].clear();
for(int j=1;j<=n;++j) {
int op;
scanf("%d",&op);
if(op) edge[i].push_back(j);
}
}
for(int i=1;i<=n;++i) {
memset(vis,false,sizeof(vis));
if(!match(i)) {
puts("No");
return ;
}
}
puts("Yes");
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
II. [洛谷T67865] - 小xzy的象棋
思路分析
把每行每列拆成若干个由棋子隔开的段，建立一张二分图 \(\m G=(\m V,\m E)\)，左部点是每个行的段，右部点是每个列的段
如果某两个段有交点，则连接这两个段对应的二分图里面的节点
原问题转化成了这个二分图上的最大匹配
事实上，\(|\m V|\) 和 \(|\m E|\) 都是 \(10^6\) 的数量级的，但是由于常数小并且复杂度完全跑不满，因此用 HK 算法可以通过本题
时间复杂度 \(\Theta(|\m E|\sqrt{|\m V|})\)
本题略卡空间，事实上，\(|\m V|\) 大概在 \([1.7\times 10^6,1.8\times 10^6]\) 之间，取 \(|\m V|=1.75\times 10^6\) 即可通过本题
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2001,MAXS=1750001;
bool a[MAXN][MAXN],vis[MAXS];
int tar[MAXS],dep[MAXS],col[MAXN][MAXN],row[MAXN][MAXN];
int L,R;
vector <int> edge[MAXS];
inline void BFS() {
memset(dep,-1,sizeof(dep));
queue <int> S;
for(int i=1;i<=L;++i) {
for(int x:edge[i]) if(tar[x]==i) goto nxt;
dep[i]=0;
S.push(i);
nxt:;
}
while(!S.empty()) {
int p=S.front();
S.pop();
for(int x:edge[p]) {
if(dep[x]!=-1||tar[x]==p) continue;
dep[x]=dep[p]+1;
if(tar[x]!=-1&&dep[tar[x]]==-1) {
dep[tar[x]]=dep[x];
S.push(tar[x]);
}
}
}
}
inline bool dfs(int p) {
if(vis[p]) return false;
vis[p]=true;
for(int x:edge[p]) {
if(vis[x]||dep[x]!=dep[p]+1) continue;
vis[x]=true;
if(tar[x]==-1||dfs(tar[x])) {
tar[x]=p;
return true;
}
}
return false;
}
inline int MM() {
memset(tar,-1,sizeof(tar));
int ret=0;
while(true) {
bool ok=false;
memset(vis,false,sizeof(vis));
BFS();
for(int i=1;i<=L;++i) {
if(dep[i]||vis[i]) continue;
if(dfs(i)) ok=true,++ret;
}
if(!ok) break;
}
return ret;
}
signed main() {
int n;
scanf("%d",&n);
memset(a,1,sizeof(a));
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
scanf("%d",&a[i][j]);
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
if(a[i][j]) continue;
if(a[i][j-1]) col[i][j]=++L;
else col[i][j]=col[i][j-1];
}
}
R=L;
for(int j=1;j<=n;++j) {
for(int i=1;i<=n;++i) {
if(a[i][j]) continue;
if(a[i-1][j]) row[i][j]=++R;
else row[i][j]=row[i-1][j];
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
if(a[i][j]) continue;
edge[col[i][j]].push_back(row[i][j]);
}
}
printf("%d\n",MM());
return 0;
}
III. [洛谷2055] - 假期的宿舍
思路分析
建立二分图 \(\m G=(\m X,\m Y,\m E)\)，床位做右部点 \(y_i\)，人做左部点 \(x_i\) ，\((x_i,y_j)\in\m E\) 当且仅当 \(i\) 能够睡在 \(j\) 的床上
当且仅当二分图中存在一个大小为 \(|\m X|\) 的匹配时存在一种合法方案，朴素求解最大匹配即可
时间复杂度 \(\Theta(n^3)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=51;
bool r[MAXN],l[MAXN],vis[MAXN];
vector <int> edge[MAXN];
int tar[MAXN];
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 solve() {
int n;
cin>>n;
for(int i=1;i<=n;++i) cin>>r[i];
for(int i=1;i<=n;++i) {
cin>>l[i]; l[i]^=1;
if(!r[i]) l[i]=true;
}
for(int i=1;i<=n;++i) {
edge[i].clear();
for(int j=1;j<=n;++j) {
bool k;
cin>>k;
if(l[i]&&r[j]&&(k||i==j)) edge[i].push_back(j);
}
}
memset(tar,-1,sizeof(tar));
for(int i=1;i<=n;++i) {
if(!l[i]) continue;
memset(vis,false,sizeof(vis));
if(!match(i)) {
puts("T_T");
return ;
}
}
puts("^_^");
}
signed main() {
int T;
cin>>T;
while(T--) solve();
return 0;
}
IV. [SGU171] - Sarov Zones
思路分析
简单贪心，按 \(w\) 值大到小考虑，对于每个人 \(i\) 选取的地区 \(j\) 应该使 \(p_i-q_j\) 尽可能小
显然可以用 set 维护地区
时间复杂度 \(\Theta(n\log n)\)
代码呈现
#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
const int MAXN=16001,MAXK=101;
int bel[MAXN];
struct student {
int p,w,id;
inline friend bool operator <(const student &x,const student &y) {
return x.w>y.w;
}
} a[MAXN];
struct region {
int q,id;
inline friend bool operator <(const region &x,const region &y) {
return x.q<y.q;
}
} f[MAXK];
int siz[MAXK];
multiset <region> S;
signed main() {
int n,k;
scanf("%d",&k);
for(int i=1;i<=k;++i) {
scanf("%d",&siz[i]);
f[i].id=i;
n+=siz[i];
}
for(int i=1;i<=k;++i) {
scanf("%d",&f[i].q);
for(int j=1;j<=siz[i];++j) S.insert(f[i]);
}
for(int i=1;i<=n;++i) {
scanf("%d",&a[i].p);
a[i].id=i;
}
for(int i=1;i<=n;++i) scanf("%d",&a[i].w);
sort(a+1,a+n+1);
for(int i=1;i<=n;++i) {
if((S.begin()->q)>=a[i].p) continue;
auto it=S.lower_bound((region){a[i].p,0});
--it;
bel[a[i].id]=it->id;
S.erase(it);
}
for(int i=1;i<=n;++i) {
if(bel[i]) printf("%d ",bel[i]);
else {
printf("%d ",S.begin()->id);
S.erase(S.begin());
}
}
puts("");
return 0;
}
V. [AGC024D] - Black and White Tree
思路分析
对于这个问题，如果后手想胜利，那么至少要保证所有色节点都至少有一个白色节点相邻
考虑对这张图 \(\m G=(\m V,\m E)\) 求出一个最大匹配 \(\m M\)
如果 \(|V(\m M)|=|\m V|\)，那么每当先手选择一个节点，后手必然可以选择其在 \(\m M\) 中与之相连的边，故若 \(\m G\) 存在完美匹配则后手有必胜策略
假如 \(|V(\m M)|<|\m V|\)，我们需要构造一个先手的必胜策略：
- 找到一个叶子节点 \(u\)，选择与 \(u\) 相连的节点 \(v\)
那么此时，如果后手不选 \(u\)，先手选 \(u\) 则最终 \(u\) 必然是白色，先手必获胜
故此时先手必然选 \(u\)，那么我们将 \(u\) 和 \(v\) 从 \(\m G\) 中删去得到集合 \(\m {G'}=(\m{V'},\m{E'})\)
注意到 \(\m{V'}\) 中没有和 \(u\) 相邻的点，因此我们可以令 \(\m {G}\gets\m{G'}\)，然后重复此操作直到不存在大小为 \(2\) 的连通块
由于 \(|V(\m M)|<|\m V|\)，所以最终的 \(\m G\) 一定存在若干个没有黑色节点相连的点，此时轮到先手操作，任选一个染成白色即可获胜
综上所述，我们证明后手能够获胜的充分必要条件是 \(\m G\) 中存在一个完美匹配
考虑无向图上最大匹配的性质：每条连接叶子结点的边都一定在最大匹配中，所以我们可以不断将新图中的叶子结点和其父亲删掉，可以求得最大匹配
时间复杂度 \(\Theta(n)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+1;
vector <int> edge[MAXN];
bool del[MAXN];
inline void dfs(int p,int f) {
for(int v:edge[p]) if(v!=f) dfs(v,p);
if(!del[p]) {
if(!f||del[f]) {
puts("First");
exit(0);
} else del[p]=del[f]=true;
}
}
signed main() {
int n;
scanf("%d",&n);
for(int i=1;i<n;++i) {
int u,v;
scanf("%d%d",&u,&v);
edge[u].push_back(v);
edge[v].push_back(u);
}
dfs(1,0);
puts("Second");
return 0;
}
VI. [CodeForces1139E] - Maximize Mex
思路分析
首先解决没有修改操作的情况，我们建立一张二分图 \(\m G=(\m X,\m Y,\m E)\)，其中 \(\m X=\{x_0,x_1,\cdots, x_{5000}\}\) 表示所有的能力值
\(0\sim 5000\)，\(\m Y={y_1,y_2,\cdots,y_m}\)，表示 \(m\) 个社团，\((x_i,y_j)\in \m E\) 当且仅当社团 \(j\) 有一个属性值为 \(i\) 的人
因此删除操作等价于在 \(\m G\) 中把一些边删除，不好维护，考虑把操作取反，问题转化为在二分图上不断加边，注意到这个时候的答案是单调递增的，因此我们只需要从上一次匹配失败的位置开始继续找增广路即可
时间复杂度 \(\Theta(dn)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5001;
int tar[MAXN];
bool vis[MAXN];
vector <int> edge[MAXN];
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;
}
int ord[MAXN],p[MAXN],bel[MAXN];
bool lst[MAXN];
set <int> soc[MAXN];
inline void newval(int s,int x) {
if(soc[s].count(x)) return ;
soc[s].insert(x);
edge[x].push_back(s);
}
int res=0,n,m,d;
inline int MM() {
for(;res<=n;++res) {
memset(vis,0,sizeof(vis));
if(!match(res)) break;
}
return res;
}
signed main() {
memset(tar,-1,sizeof(tar));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d",&p[i]);
for(int i=1;i<=n;++i) scanf("%d",&bel[i]);
scanf("%d",&d);
for(int i=1;i<=d;++i) {
int k;
scanf("%d",&k);
ord[d-i+1]=k;
lst[k]=true;
}
vector <int> ans;
for(int i=1;i<=n;++i) {
if(!lst[i]) newval(bel[i],p[i]);
}
ans.push_back(MM());
for(int i=1;i<d;++i) {
newval(bel[ord[i]],p[ord[i]]);
ans.push_back(MM());
}
reverse(ans.begin(),ans.end());
for(auto a:ans) printf("%d\n",a);
return 0;
}
VII. [BZOJ2437] - 兔兔与蛋蛋
思路分析
黑子和白子都不独特，但是空格只有一个，因此应该重点关注空格，我们把棋子移动到空格上变成空格移动到棋子上
这个时候看到棋盘问题，我们可以考虑黑白间隔染色，假设空格最开始在黑色格子上，那么每次移动的时候空格可以移动到黑色格子的黑色棋子上或者白色格子的白色棋子上（假设空格上有一枚黑色棋子）
假如我们此时对所有能互相到达的格子之间连边，那么这张图就是一张二分图
空格每次移动会交换两枚棋子的位置，注意到每次交换一定会让黑色棋子移动到白色格子上，白色棋子移动到黑色格子上，因此每当我们考虑完一个移动的操作，我们只需要把这个点从二分图中删掉即可
原问题转化成在二分图上，双方轮流移动棋子，不能重复经过节点，移动不了的输，可以发现这就是第一节中的 UVG 游戏，套结论：当且仅当空格在二分图最大匹配的一个必经点上，那么先手胜
因此对于每次移动：我们考虑原来二分图的最大匹配和删掉当前位置的二分图的最大匹配，当且仅当这两个东西不相等的时候先手有必胜策略
注意删掉点之后需要更新最大匹配的大小
对于每个格子暴力做二分图最大匹配即可解决此问题
时间复杂度 \(\Theta(kn^2m^2)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=41,MAXS=1601,MAXK=1001;
int n,m,dx[]={0,0,1,-1},dy[]={1,-1,0,0};
int tar[MAXS];
bool vis[MAXS],win[MAXK];
bool bel[MAXN][MAXN],col[MAXN][MAXN],del[MAXS];
vector <int> edge[MAXS],src;
inline int id(int x,int y) {
if(x<1||x>n||y<1||y>m||bel[x][y]!=col[x][y]) return -1;
return (x-1)*m+y;
}
inline bool match(int p) {
if(del[p]) return false;
for(int x:edge[p]) {
if(vis[x]||del[x]) continue;
vis[x]=true;
if(tar[x]==-1||match(tar[x])) {
tar[x]=p;
return true;
}
}
return false;
}
inline int MM() {
int ret=0;
memset(tar,-1,sizeof(tar));
for(int x:src) {
memset(vis,false,sizeof(vis));
if(match(x)) ++ret;
}
return ret;
}
signed main() {
int kx,ky;
cin>>n>>m;
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
char ch;
cin>>ch;
if(ch=='.') kx=i,ky=j,bel[i][j]=true;
else bel[i][j]=(ch=='X');
}
}
for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) col[i][j]=((i+j)%2==(kx+ky)%2);
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
if(bel[i][j]&&col[i][j]) {
src.push_back(id(i,j));
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 stdv=MM(),k;
del[id(kx,ky)]=true;
int tmpv=MM();
win[1]=tmpv!=stdv;
stdv=tmpv;
scanf("%d",&k);
vector <int> ans;
for(int i=1;i<=k;++i) {
int tx,ty;
scanf("%d%d",&tx,&ty);
del[id(tx,ty)]=true;
tmpv=MM();
win[i*2]=tmpv!=stdv;
stdv=tmpv;
if(win[i*2]&&win[i*2-1]) ans.push_back(i);
scanf("%d%d",&tx,&ty);
del[id(tx,ty)]=true;
tmpv=MM();
win[i*2+1]=tmpv!=stdv;
stdv=tmpv;
}
printf("%d\n",(int)ans.size());
for(int p:ans) printf("%d\n",p);
return 0;
}
五、思考题
I. 思考题一
题目大意
如何判定二分图 \(\m G\) 的最大匹配是唯一的？复杂度？
思路分析
- 枚举最大匹配的每个边是否是必须的，时间复杂度 \(\Theta(nm^2)\)（增广轨算法）或者 \(\Theta(m^2\sqrt n)\)（HK 算法）
提供一中更优的做法：求出 \(\m G\) 的一个最大匹配 \(\m M\)，假如此时存在某条交错轨 \(\m A\)，其一端不在 \(V(\m M)\) 中，或者存在一个交错环 \(\m A\)，那么 \(\m M\oplus \m A\) 也是一个大小为 \(|\m M|\) 的最大匹配，此时最大匹配不唯一，否则唯一
注意到这个交错轨的求法只需要通过一次类似 HK 算法过程中的 BFS 即可，故我们能够得到一个 \(\Theta(m\sqrt n)\) 的算法，瓶颈在求最大匹配的过程中
II. 思考题一
题目大意
如何判定 \(\m G\) 中的每条边是否一定在 \(\m G\) 的最大匹配中？请你给出比 \(\Theta(nm^2)\) 更快的算法
思路分析
先对原图的无向边都转化成的有向边：若 \((x_i,y_j)\not\in \m M\)，则连接 \(x_i\to y_j\)，否则连接 \(y_j\to x_i\)（其实就是找增广轨的搜索顺序）
如何快速统计交错轨：一遍 BFS 标记每个 Free-Point 能通过交错轨到达哪些点，然后判断两端是否能到达同一个 Free-Point 即可
此时交错环会变成这个这个图中的一个环，因此只需要对这个有向图缩点，判断每条边的两个端点在不在一个强连通分量中，如果不在，那么这条边是 \(\m G\) 的最大匹配的一条必经边
时间复杂度 \(\Theta(n+m)\)
III. 思考题三
题目大意
给定一个无向图，\(n\) 个点，边长都为 \(1\)，请计算 \(1\) 到 \(n\) 的最短的长度为偶数的简单路
思路分析
目前还没有做出来。。。
挖坑，待补
