二分图（三）
\(\newcommand \m \mathbf\)
\(\text{By DaiRuiChen007}\)
一、Dilworth 定理
I. 相关定义
对于一个集合 \(\m S\)，定义 \(\m S\) 上的一种偏序关系 \(\succsim\) 满足以下三条关系：
- \(A\succsim A\)
- 若 \(A\succsim B\) 且 \(B\succsim A\)，则 \(A=B\)
- 若 \(A\succsim B\) 且 \(B\succsim C\)，则 \(A\succsim C\)
那么关系 \(\succsim\) 就是 \(\m S\) 的一个偏序关系，\(\m S\) 就是一个偏序集
注意：并不是任意两个元素之间都存在偏序关系，即不是每两个 \(\m S\) 里的元素都能够比较出大小
类似的，我们可以定义一个严格偏序关系 \(\succ\)：
- \(A\succ B\) 当且仅当 \(A\succsim B\) 且 \(A\ne B\)
在偏序集 \(\m S\) 上，我们对于所有 \(A\succ B\) 连一条 \(A\to B\) 的边，结果一定是一个 DAG（证明略）
如果我们把这个 DAG 的最小链剖分 \(\m P\) 求出来，那么 \(\m P\) 也称作 \(\m S\) 的最小链划分
如果我们选出一个 \(\m S\) 的子集 \(\m A\) 满足 \(\m A\) 中任意两个元素都不存在偏序关系，那么我们称 \(\m A\) 是 \(\m S\) 的一个反链
II. Dilworth 定理
Dilworth 定理是：在偏序集上，最小链划分的大小等于最大反链的大小
如果我们即最小链划分为 \(\m P\)，最大反链为 \(\m A\)，那么 Dilworth 定理指的是 \(|\m P|=|\m A|\)
III. 证明
假设最小链划分为 \(\m P^\star\)，最大反链为 \(\m A^\star\)
首先，我们能够证明 \(\forall \m A,\m P:|\m P|\ge|\m A|\)，其中 \(\m P,\m A\)，是任意的链划分和反链
证明很简单：假设 \(|\m P|<|\m A|\)，那么根据抽屉原理，至少有两个 \(\m A\) 中的元素在同一条链中，但这两个元素之间没有偏序关系（反链定义），因此矛盾，故原命题得证
那么我们对这个偏序集求出最小链分割，显然考虑建立二分图 \(\m G=(\m X,\m Y,\m E)\)，\((x_i,y_j)\in\m E\iff A_i\succ A_j\)
根据之前的结论，如果记 \(\m M\) 为 \(\m G\) 的最大匹配，那么 \(|\m P^\star|=|\m S|-|\m M|\)
然后，我们求出一个 \(\m G\) 的最小覆盖集 \(\m{VC}\)，根据之前的 Konig 定理得到：\(|\m {VC}|=|\m M|\)，我们构造一个集合 \(\m A=\{u|x_u\not\in \m{VC}\land y_u\not\in\m{VC}\}\)，即所有 \(x_u,y_u\) 均不属于 \(\m{VC}\) 的 \(u\) 构成的集合
假如这些 \(u\) 中有一些之间存在偏序关系，那么就立刻得到 \(\m {VC}\) 之外还有边，与 \(\m {VC}\) 是覆盖集矛盾，因此 \(\m A\) 是 \(\m S\) 的一个反链，并且 \(|\m A|\ge |\m S|-|\m M|\)
又因为 \(\forall \m A,\m P:|\m P|\ge |\m A|\)，所以 \(|\m A|=|\m S|-|\m M|=|\m P^\star|\)，且不存在更小的反链，否则其大小就会小于 \(|\m P^\star|\)，与引理矛盾
因此 \(|\m A^\star|=|\m P^\star|\)，证明完毕
IV. 习题演练
思路分析
考虑计算最大反链，即对于所有 \(x_i<x_j,y_i>y_j\) 的 \((i,j)\) 构成无偏序关系的两个元素，因此我们选出的这个反链一定是 \(x\) 严格递增时 \(y\) 严格递降，然后最大化选出的点的 \(a\) 的和
因此用 \(dp_{i,j}\) 维护选择了 \((i,j)\) 之后的最大和，显然简单树状数组维护一下能够做到 \(\Theta(nm\log m)\)，当然也可以简单前缀和一下做到 \(\Theta(nm)\)，具体的实现可以自行想一想
代码呈现
树状数组版：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e3+1;
int n,m;
int dp[MAXN][MAXN],a[MAXN][MAXN];
class BITTree {
private:
int tr[MAXN];
inline int lowbit(int x) { return x&-x; }
public:
BITTree() { memset(tr,0,sizeof(tr)); }
inline void Modify(int p,int x) {
for(;p<=m;p+=lowbit(p)) tr[p]=max(tr[p],x);
}
inline int Query(int p) {
int ret=0;
for(;p;p-=lowbit(p)) ret=max(ret,tr[p]);
return ret;
}
};
inline void solve() {
BITTree A;
memset(dp,0,sizeof(dp));
int ans=0;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
scanf("%lld",&a[i][j]);
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) dp[i][j]=A.Query(m-j)+a[i][j],ans=max(ans,dp[i][j]);
for(int j=1;j<=m;++j) A.Modify(m-j+1,dp[i][j]);
}
printf("%lld\n",ans);
return ;
}
signed main() {
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}
前缀和版：
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=1e3+1;
int n,m;
int dp[MAXN][MAXN],a[MAXN][MAXN];
inline void solve() {
int ans=0;
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;++i) {
for(int j=1;j<=m;++j) {
scanf("%lld",&a[i][j]);
}
}
for(int i=1;i<=n;++i) {
int f=0;
for(int j=m;j>=1;--j) {
dp[i][j]=max(f+a[i][j],dp[i-1][j]);
ans=max(ans,dp[i][j]);
f=max(f,dp[i-1][j]);
}
}
printf("%lld\n",ans);
return ;
}
signed main() {
int T;
scanf("%lld",&T);
while(T--) solve();
return 0;
}
二、二分图最大权完美匹配
I. 定义
对于一张二分图 \(\m G=(\m X,\m Y,\m E)\)，满足 \(|\m X|=|\m Y|\) 且 \(\forall x_i\in \m X,y_j\in \m Y:(x_i,y_i)\in\m E\)（任意两点之间都有边），其最大权完美匹配定义为其边权和最大的完美匹配
对于一张一般的二分图，我们可以通过加入若干个点并且把没连的边的边加入边权为 \(0\) 的边使其变成一张合法的二分图
这里介绍的算法是 KM 算法，又称匈牙利算法，可以在 \(\Theta(|\m X|^3)\) 的时间复杂度内解决二分图最大权完美匹配问题
在 KM 算法中，有两个非常重要的概念：可行顶标和相等子图
可行顶标：一个可行顶标 \(L\) 对于每个点给定一个权值 \(l_x,l_y\)，需要满足 \(\forall x,y:l_x+l_y\ge w(x,y)\)
相等子图：\(\m G\) 的一个子图，所有满足 \(l_x+l_y=w(x,y)\) 的边构成的子图
II. 重要结论
KM 算法的核心由以下结论给出：
对于某个 \(\m G\) 的相等子图 \(\m G_L\)，如果其有一个完美匹配（大小为 \(|\m X|\) 的匹配 ）\(|\m M|\)，那么 \(\m M\) 一定是一个 \(\m G\) 的最大权完美匹配
根据相等子图和完美匹配的定义，我们可以得到：\(cost(\m M)=\sum_{x\in\m X}l_x+\sum _{y\in\m Y} l_y\)
根据可行顶标的定义，对于 \(\m G\) 的每一个完美匹配（不一定是 \(\m G_L\) 的完美匹配）\(\m {M'}\)都有 \(cost(\m {M'})\le cost(L)=cost(\m M)\)
III. KM 算法
朴素的 KM 算法流程大致如下：
其中 \(\m S\) 的定义和前面 HK 的内容里一样，维护交错轨终点的集合
IV. 复杂度分析
KM 算法复杂度的核心在 12 行的循环执行的次数
注意到我们每次循环用 \(\delta\) 更新 \(L\) 时都不会改变 \(\m G_L\) 中 \(\m {S_X}\) 和 \(\m {S_Y}\) 之间的边，并且至少有一条 \(\m{S_X}\) 和 \(\m{T_Y}\) 之间的边 \((x,y)\) 在操作结束之后会有：\(l_{x}+l_{y}=w(x,y)\)，然后加入 \(\m G_L\) 中，我们对 \(y\) 进行讨论
- \(y\not\in V(\m M)\)，此时我们直接把 \(y\) 加入 \(\m {S_Y}\) 中，显然 \(y\) 会作为某一条交错轨的终点，拓展结束
- \(y\in V(\m M)\)，设 \((x',y)\in \m M\)，则把 \(x'\) 加入 \(\m{S_X}\)，\(y\) 加入 \(\m {S_Y}\)，此时 \(|\m{S_x}|,|\m{S_Y}|\) 至少增加 \(1\)，又 \(\m{S_X}\subseteq\m X\)，因此 12 行的循环至多执行 \(\Theta(|\m X|)\) 次
此时，我们得到了一个复杂度为 \(\Theta(|\m X|^4)\) 的算法，我们需要进行进一步优化
V. 优化
注意到时间复杂度的瓶颈在求 \(\delta\) 上，因此我们可以对于每个 \(\m{T_Y}\) 中的 \(y\) 维护一个 \(slack_y=\min_{x\in\m{S_X}}\{l_x+l_y-w(x,y)\}\)
此时 \(\delta=\min_{y\in\m{T_Y}}\{slack_y\}\)，因此求 \(\delta\) 的过程时间复杂度优化到了 \(\Theta(|\m X|)\)，总时间复杂度为 \(\Theta(|\m X|^3)\)
优化后的 KM 算法流程如下：
VI. 代码呈现
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN=401,INF=1e18;
int w[MAXN][MAXN],slack[MAXN],lx[MAXN],ly[MAXN],tar[MAXN],res[MAXN];
bool sx[MAXN],sy[MAXN];
int n,m;
inline bool find(int x) {
if(sx[x]) return false;
sx[x]=true;
for(int y=1;y<=n;++y) {
if(sy[y]) continue;
int k=lx[x]+ly[y]-w[x][y];
if(!k) {
sy[y]=true;
if(tar[y]==-1||find(tar[y])) {
tar[y]=x;
return true;
}
} else slack[y]=min(slack[y],k);
}
return false;
}
inline int match() {
memset(tar,-1,sizeof(tar));
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
for(int x=1;x<=n;++x) {
for(int y=1;y<=n;++y) {
lx[x]=max(lx[x],w[x][y]);
}
}
for(int x=1;x<=n;++x) {
memset(slack,0x3f,sizeof(slack));
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
if(find(x)) continue;
while(true) {
int delta=INF,y=0;
for(int i=1;i<=n;++i) if(!sy[i]) delta=min(delta,slack[i]);
for(int i=1;i<=n;++i) {
if(sx[i]) lx[i]-=delta;
if(sy[i]) ly[i]+=delta;
else {
slack[i]-=delta;
if(!slack[i]) y=i;
}
}
if(tar[y]==-1) break;
int x=tar[y];
sx[x]=sy[y]=true;
for(int i=1;i<=n;++i) slack[i]=min(slack[i],lx[x]+ly[i]-w[x][i]);
}
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
find(x);
}
int ret=0;
for(int i=1;i<=n;++i) ret+=w[tar[i]][i];
return ret;
}
signed main() {
int nx,ny;
scanf("%lld%lld%lld",&ny,&nx,&m);
n=max(nx,ny);
for(int i=1;i<=m;++i) {
int u,v,val;
scanf("%lld%lld%lld",&v,&u,&val);
w[u][v]=val;
}
printf("%lld\n",match());
for(int i=1;i<=ny;++i) printf("%lld ",w[tar[i]][i]?tar[i]:0ll);
puts("");
return 0;
}
VII. 推论
对于 \(cost(L)\) 最小的一组可行顶标 \(L^\star\)，和最大权完美匹配 \(\m M^\star\)，不管 \(\m M^\star\) 是不是 \(\m G_{L^\star}\) 的一个匹配，都一定有 \(cost(\m M^\star)=cost(L^\star)\)
首先，我们知道对于任意一组可行顶标 \(L\)，由于可行顶标的定义，\(cost(L)\) 一定大于任意一个匹配 \(\m M\) 的权值
所以我们只需要构造一组 \(L\) 和 \(\m M\)，使得 \(cost(L)=cost(\m M)\)，那么我们就能够证明 \(L\) 一定是最小的可行顶标，\(\m M\) 一定是一个最大权的匹配，显然 KM 算法最终求解的答案就满足此要求，故该推论得证
VIII. 习题演练
记生成树为 \(\m T\)，首先，我们知道对于所有 \(e\in \m T\)，\(d(e)\le c(e)\)，否则 \(d(e)\ge c(e)\)，不妨记 \(|d(e)-c(e)|=\Delta(e)\)，那么我们的目标就是最小化 \(\sum_{e\in \m E}\Delta(e)\)
考虑什么时候 \(\m T\) 是一棵 MST：对于所有非树边 \(e'\)，其加入 \(\m T\) 后会构成一个环，当且仅当这个环上的所有边 \(e\) 都有 \(d(e)\le d(e')\) 时成立，记 \(cyc(e')\) 为加入 \(e'\) 后构成的环中的树边集，那么有：
\[\begin{aligned} \forall e\in cyc(e'): \\d(e)&\le d(e')\\ \iff c(e)-\Delta(e)&\le c(e')+\Delta(e)\\ \iff \Delta(e)+\Delta(e')&\ge c(e)-c(e') \end{aligned} \]已知 \(c(e)-c(e')\) 是定值，假如我们把边抽象成二分图中的点，树边为左部点，非树边为右部点，并且赋 \(w(e,e')=c(e)-c(e')\)，那么 \(\Delta\) 就会变成可行顶标
根据 KM 算法的推论，最小可行顶标和等于最大权匹配，所以我们只需要求出这张二分图的最大权完美匹配即可
时间复杂度 \(\Theta(m^3)\)
#include<bits/stdc++.h>
using namespace std;
const int MAXN=61,MAXM=401,INF=1e9;
struct node {
int des,id;
};
vector <node> edge[MAXN];
int n,m;
int dep[MAXN],fa[MAXN],fid[MAXN],c[MAXM];
inline void dfs(int p,int f,int id) {
dep[p]=dep[f]+1,fa[p]=f,fid[p]=id;
for(auto e:edge[p]) {
int v=e.des;
if(v==f) continue;
dfs(v,p,e.id);
}
}
int w[MAXM][MAXM],slack[MAXM],lx[MAXM],ly[MAXM],tar[MAXM];
bool sx[MAXM],sy[MAXM];
inline bool find(int x) {
if(sx[x]) return false;
sx[x]=true;
for(int y=1;y<=m;++y) {
if(sy[y]) continue;
int k=lx[x]+ly[y]-w[x][y];
if(!k) {
sy[y]=true;
if(tar[y]==-1||find(tar[y])) {
tar[y]=x;
return true;
}
} else slack[y]=min(slack[y],k);
}
return false;
}
inline void KM() {
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
memset(tar,-1,sizeof(tar));
for(int i=1;i<=m;++i) {
for(int j=1;j<=m;++j) {
lx[i]=max(lx[i],w[i][j]);
}
}
for(int t=1;t<=m;++t) {
memset(slack,0x3f,sizeof(slack));
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
if(find(t)) continue;
while(true) {
int delta=INF,y=0;
for(int i=1;i<=m;++i) if(!sy[i]) delta=min(delta,slack[i]);
for(int i=1;i<=m;++i) {
if(sx[i]) lx[i]-=delta;
if(sy[i]) ly[i]+=delta;
else {
slack[i]-=delta;
if(!slack[i]) y=i;
}
}
if(tar[y]==-1) break;
int x=tar[y];
sx[x]=sy[y]=true;
for(int i=1;i<=m;++i) slack[i]=min(slack[i],lx[x]+ly[i]-w[x][i]);
}
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
find(t);
}
}
signed main() {
scanf("%d%d",&n,&m);
for(int i=1;i<n;++i) {
int u,v;
scanf("%d%d%d",&u,&v,&c[i]);
edge[u].push_back((node){v,i});
edge[v].push_back((node){u,i});
}
dfs(1,0,0);
for(int i=n;i<=m;++i) {
int u,v;
scanf("%d%d%d",&u,&v,&c[i]);
while(u!=v) {
if(dep[u]<dep[v]) swap(u,v);
w[fid[u]][i]=max(0,c[fid[u]]-c[i]);
u=fa[u];
}
}
KM();
for(int i=1;i<n;++i) printf("%d\n",c[i]-lx[i]);
for(int i=n;i<=m;++i) printf("%d\n",c[i]+ly[i]);
return 0;
}
三、习题演练
[洛谷5939] - 折线
思路分析
把每个点逆时针旋转 \(45^\circ\)，让所有的 \((x,y)\) 变成 \((x+y,x-y)\)
原题转成 \(x_i\le x_j,y_i\ge y_j\) 的覆盖，然后 Dilworth 定理一下，等价于求出最大的二维上升子序列，按 \(x\) 排序之后变成导弹拦截，dp 求解即可
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=3e4+1;
struct node {
int x,y;
inline friend bool operator <(const node &A,const node &B) {
return A.x==B.x?A.y>B.y:A.x<B.x;
}
} a[MAXN];
int k[MAXN];
signed main() {
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;++i) {
int ix,iy;
scanf("%d%d",&ix,&iy);
a[i]=(node){ix+iy,iy-ix};
}
sort(a+1,a+n+1);
k[++ans]=a[1].y;
for(int i=2;i<=n;++i) {
if(a[i].y>k[ans]) k[++ans]=a[i].y;
k[lower_bound(k+1,k+ans+1,a[i].y)-k]=a[i].y;
}
printf("%d\n",ans);
return 0;
}
[CodeForces590E] - Birthday
思路分析
简单题，首先建立偏序关系 \(S_i \succ S_j\) 当且仅当 \(S_j\) 是 \(S_i\) 的一个子串，问题等价于求这个偏序集的最大反链
显然，通过偏序关系建立二分图并且根据上面的讲解内容求出最大反链即可
因此原问题转化为快速求出所有子串关系，显然可以用 AC 自动机来解决这个问题
为了保证复杂度，需要做一个小优化：对于每个位置跳失配指针只需要跳到第一个完整串的结尾，而不是一直跳到根节点，否则可能会超时或者爆栈
在连接完整串的结尾之后，通过一遍 Floyd 传递闭包即可建出完整的偏序集
时间复杂度 \(\Theta(n^3+\sum_{i=1}^n|S_i|)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=751,MAXS=1e7+1;
bool link[MAXN][MAXN];
string str[MAXN];
class Trie {
private:
struct node {
int s[2],fail,id,lst;
node() { s[0]=s[1]=fail=id=lst=0; }
} tr[MAXS];
int tot;
inline int find(int x) {
if(tr[x].lst==x) return x;
return tr[x].lst=find(tr[x].lst);
}
public:
inline void insert(int id) {
int p=0;
for(auto ch:str[id]) {
int u=ch-'a';
if(!tr[p].s[u]) tr[p].s[u]=++tot;
p=tr[p].s[u];
}
tr[p].id=id;
}
inline void build() {
queue <int> q;
if(tr[0].s[0]) q.push(tr[0].s[0]);
if(tr[0].s[1]) q.push(tr[0].s[1]);
while(!q.empty()) {
int p=q.front();
q.pop();
for(int u:{0,1}) {
if(tr[p].s[u]) {
tr[tr[p].s[u]].fail=tr[tr[p].fail].s[u];
q.push(tr[p].s[u]);
} else tr[p].s[u]=tr[tr[p].fail].s[u];
}
}
for(int p=1;p<=tot;++p) {
if(!tr[p].id) tr[p].lst=tr[p].fail;
else tr[p].lst=p;
}
}
inline void substr(int id) {
int p=0;
for(char ch:str[id]) {
int u=ch-'a',x=find(p);
if(tr[x].id) link[id][tr[x].id]=true;
p=tr[p].s[u];
}
int x=find(tr[p].fail);
if(tr[x].id) link[id][tr[x].id]=true;
}
} T;
vector <int> edge[MAXN];
int tar[MAXN];
bool sx[MAXN],sy[MAXN];
inline bool dfs(int p) {
if(sx[p]) return false;
sx[p]=true;
for(int x:edge[p]) {
if(sy[x]) continue;
sy[x]=true;
if(tar[x]==-1||dfs(tar[x])) {
tar[x]=p;
return true;
}
}
return false;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int n;
cin>>n;
for(int i=1;i<=n;++i) {
cin>>str[i];
T.insert(i);
}
T.build();
for(int i=1;i<=n;++i) T.substr(i),link[i][i]=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];
}
}
}
for(int i=1;i<=n;++i) {
for(int j=1;j<=n;++j) {
if(link[i][j]&&i!=j) edge[i].push_back(j);
}
}
vector <int> ret;
memset(tar,-1,sizeof(tar));
for(int i=1;i<=n;++i) {
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
dfs(i);
}
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
for(int i=1;i<=n;++i) {
for(int j:edge[i]) if(tar[j]==i) goto Fail;
dfs(i);
Fail:;
}
for(int i=1;i<=n;++i) if(sx[i]&&!sy[i]) ret.push_back(i);
cout<<ret.size()<<'\n';
for(int x:ret) cout<<x<<' ';
cout<<'\n';
return 0;
}
[洛谷3845] - 球赛
思路分析
把所有可能互相承接的比分建立偏序关系，问题即求最大反链
注意到比分 \(a:b\) 在 \(a':b'\) 之后当且仅当 \(\min(a,b)\le \min(a',b'),\max(a,b)\le \max(a',b')\)，因此可以转成类似第一题的上升子序列，时间复杂度 \(\Theta(s\log s)\) 或 \(\Theta(s^2)\)
当然也可以建立二分图之后用 Dilworth 转成最小链剖分，用 HK 解可以得到 \(\Theta(s^{2.5})\) 的复杂度
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1001;
vector <int> edge[MAXN];
int dx[MAXN],dy[MAXN],tar[MAXN],n;
bool sx[MAXN],sy[MAXN];
inline void bfs() {
memset(dx,0x3f,sizeof(dx));
memset(dy,0x3f,sizeof(dy));
queue <int> q;
for(int i=1;i<=n;++i) {
for(int j:edge[i]) if(tar[j]==i) goto Fail;
dx[i]=0; q.push(i);
Fail:;
}
while(!q.empty()) {
int p=q.front();
q.pop();
for(int x:edge[p]) {
if(dy[x]<=dx[p]+1) continue;
dy[x]=dx[p]+1;
if(tar[x]!=-1) {
if(dx[tar[x]]<=dy[x]) continue;
dx[tar[x]]=dy[x];
q.push(tar[x]);
}
}
}
}
inline bool dfs(int p) {
if(sx[p]) return false;
sx[p]=true;
for(int x:edge[p]) {
if(sy[x]||dy[x]!=dx[p]+1) continue;
sy[x]=true;
if(tar[x]==-1||dfs(tar[x])) {
tar[x]=p;
return true;
}
}
return false;
}
inline int HK() {
memset(tar,-1,sizeof(tar));
int ret=0;
while(true) {
bool ok=false;
bfs();
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
for(int i=1;i<=n;++i) if(!dx[i]&&!sx[i]) if(dfs(i)) ++ret,ok=true;
if(!ok) break;
}
return ret;
}
pair <int,int> p[MAXN];
inline void solve() {
scanf("%d",&n);
for(int i=1;i<=n;++i) {
int x,y;
scanf("%d-%d",&x,&y);
p[i]=make_pair(min(x,y),max(x,y));
}
sort(p+1,p+n+1);
n=unique(p+1,p+n+1)-p-1;
for(int i=1;i<=n;++i) {
edge[i].clear();
for(int j=1;j<=n;++j) {
if(p[i].first>=p[j].first&&p[i].second>=p[j].second) {
if(i!=j) edge[i].push_back(j);
}
}
}
printf("%d\n",n-HK());
}
signed main() {
int T;
scanf("%d",&T);
while(T--) solve();
return 0;
}
[UVA1411] - Ants
思路分析
将每个黑点和白点连一条权值为其距离的边，最小匹配即为所求
证明如下：
假设 \(\m M\) 是一个距离和最小的匹配方案
若 \(\m M\) 中两条边 \((x_i,y_i)\) 与 \((x_j,y_j)\) 相交，根据句三角形两边之和大于第三边，\((x_i,y_j)\) 和 \((x_j,y_i)\) 的距离和一定更小，因此与 \(\m M\) 是最小匹配矛盾
故 \(\m M\) 中没有边相交，原命题得证
时间复杂度 \(\Theta(n^3)\)
代码呈现
#include<bits/stdc++.h>
using namespace std;
const int MAXN=101;
const double EPS=1e-7,INF=1e9;
double lx[MAXN],ly[MAXN],slack[MAXN],w[MAXN][MAXN];
int tar[MAXN],n;
bool sx[MAXN],sy[MAXN];
inline bool find(int x) {
if(sx[x]) return false;
sx[x]=true;
for(int y=1;y<=n;++y) {
if(sy[y]) continue;
double k=lx[x]+ly[y]-w[x][y];
if(fabs(k)<=EPS) {
sy[y]=true;
if(tar[y]==-1||find(tar[y])) {
tar[y]=x;
return true;
}
} else slack[y]=min(slack[y],k);
}
return false;
}
inline void KM() {
for(int i=1;i<=n;++i) lx[i]=-INF,ly[i]=0;
memset(tar,-1,sizeof(tar));
for(int x=1;x<=n;++x) for(int y=1;y<=n;++y) lx[x]=max(lx[x],w[x][y]);
for(int t=1;t<=n;++t) {
for(int i=1;i<=n;++i) slack[i]=INF;
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
if(find(t)) continue;
while(true) {
double delta=INF; int y=0;
for(int i=1;i<=n;++i) if(!sy[i]) delta=min(delta,slack[i]);
for(int i=1;i<=n;++i) {
if(sx[i]) lx[i]-=delta;
if(sy[i]) ly[i]+=delta;
else {
slack[i]-=delta;
if(fabs(slack[i])<=EPS) y=i;
}
}
if(tar[y]==-1) break;
int x=tar[y];
sx[x]=true,sy[y]=true;
for(int i=1;i<=n;++i) slack[i]=min(slack[i],lx[x]+ly[i]-w[x][i]);
}
memset(sx,false,sizeof(sx));
memset(sy,false,sizeof(sy));
find(t);
}
}
int x[MAXN],y[MAXN];
signed main() {
while(scanf("%d",&n)!=EOF){
for(int i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]);
for(int i=1;i<=n;++i) {
int tx,ty;
scanf("%d%d",&tx,&ty);
for(int j=1;j<=n;++j) w[i][j]=-sqrt((x[j]-tx)*(x[j]-tx)+(y[j]-ty)*(y[j]-ty));
}
KM();
for(int i=1;i<=n;++i) printf("%d\n",tar[i]);
}
return 0;
}