二分图最大匹配
匈牙利算法
增广路：在二分图中的一条路径，起始点和终末点都是未匹配点，边按照 未匹配边-匹配边-未匹配边-.....匹配边-未匹配边交替相连(显然其他点都是匹配点)。
匈牙利算法的核心就是不断在图中寻找增广路，找到了就将路上的匹配边变为未匹配边，未匹配边变为匹配边，这样当前的匹配就增加了1，直到找不到为止。
如何实现这个过程？
-
由于起始点是未1匹配点，每次都要寻找新的未匹配点
-
遍历这个点的所有邻接点，若邻接点未匹配，则直接加入匹配，若已经匹配，则尝试让邻接点的匹配点寻找别的匹配点，让出这个点给当前点。(显然这是一个递归的过程)
#include <bits/stdc++.h>
using namespace std;
const int maxnx=1e3+5;
const int maxny=1e3+5;
const int maxm=2e6+5;
int nx,ny,m;
int my[maxny];
int vis[maxnx];
struct edge{
int next,to;
}E[maxm];
int tot=0,head[maxnx];
void addedge(int u,int v){
E[++tot].to=v;
E[tot].next=head[u];
head[u]=tot;
}
int find_path(int u){
if(vis[u])return 0;
vis[u]=1;
for(int i=head[u];i>0;i=E[i].next){
int v=E[i].to;
if(my[v]==0||find_path(my[v])){
my[v]=u;
return 1;
}
}
return 0;
}
int main(){
int nx,ny,m;
cin>>nx>>ny>>m;
for(int i=1;i<=m;i++){
int u,v;//u,v可以有重复的标号
scanf("%d%d",&u,&v);
if(u>nx||v>ny) continue;//洛谷数据问题
addedge(u,v);
}
int ans=0;
for(int i=1;i<=nx;i++){
memset(vis,0,sizeof(vis));//如果nx较大,可以采用i作为标记的方法节约时间
if(find_path(i)){
ans++;
}
}
printf("%d
",ans);
}
dinic优化二分图最大匹配
Dinic算法的时间复杂度的理论上界是(O(N^2*M))（N是结点数，M是边数），但实际上Dinic算法比这个理论上界好得多。如果所有边容量均为1，那么时间复杂度是(O(min(N^{0.67},M^{0.5}) * M))；对于二分图最大匹配这样的特殊图，时间复杂度是(O(sqrt{N}* M))
#include <bits/stdc++.h>
using namespace std;
const int maxm=2e6+5;
const int maxn=1e4+5;
struct edge{
int to,next,w;
}E[maxm];
int tot=1,head[maxn],cur[maxn];
void addedge(int u,int v,int w){
E[++tot].to=v;
E[tot].w=w;
E[tot].next=head[u];
head[u]=tot;
}
int n,m,s,t;
int dep[maxn],q[maxn];
bool bfs(){
fill(dep,dep+1+n,0);
int l=0,r=1;
q[r]=s;
dep[s]=1;
while(l!=r){
int u=q[l=l==n?0:l+1];
for(int i=head[u];i;i=E[i].next){
int v=E[i].to;
if(E[i].w&&!dep[v]){
dep[v]=dep[u]+1;
q[r=r==n?0:r+1]=v;
}
}
}
return dep[t]>0;
}
int dfs(int u,int in){
if(u==t)
return in;
int out=0;
for(int i=cur[u];i&∈i=E[i].next){
cur[u]=i;
int v=E[i].to;
if(E[i].w&&dep[v]==dep[u]+1){
int res=dfs(v,min(E[i].w,in));
E[i].w-=res;
E[i^1].w+=res;
in-=res;
out+=res;
}
}
if(out==0)dep[u]=-1;//该点无法到达终点
return out;
}
void add(int u,int v,int w){
addedge(u,v,w);
addedge(v,u,0);
}
int maxf;
void dinic(){
maxf=0;
while(bfs()){
for(int i=1;i<=n;i++)cur[i]=head[i];
maxf+=dfs(s,2e9);
}
}
int main(){
int e,nn,mm;
cin>>nn>>mm>>e;
s=nn+mm+1;
t=nn+mm+2;
n=nn+mm+2;
for(int i=1;i<=e;i++){
int u,v;
scanf("%d%d",&u,&v);
if(u>nn||v>mm)continue;//洛谷数据问题
add(u,nn+v,1);
}
for(int i=1;i<=nn;i++){
add(s,i,1);
}
for(int i=nn+1;i<=nn+mm;i++){
add(i,t,1);
}
dinic();
printf("%d
",maxf);
}
例题
变换序列(匈牙利算法)
题意简化为：二分图的左部为0n-1,右部也为0n-1，左部的点都有两条边连向右部，问最大匹配是否为n，若匹配为n，则求字典序最小的mx[0]，mx[1]....mx[n-1]序列(mx[i]为左部点i的匹配点)
显然要求最大匹配是很容易的，难点在于如何保证字典序最小。考虑匈牙利算法的特性，如果一个点相邻的匹配点可以退避就必须退避来让出给新的点。
如果从前向后，优先匹配最小的右部点，那之后会被后面的点强制退避掉，肯定不能达到最优解。
如果从后向前，优先匹配最小的右部点，这样的话序号小的点也是优先匹配最小的右部点，如果能退避就让序号大的退避掉，贪心地保证了序号小的左部点优先匹配到序号小的右部点。
#include <bits/stdc++.h>
using namespace std;
const int maxn=1e4+5;
const int maxnx=1e4+5;
const int maxny=1e4+5;
const int maxm=1e6+5;
int nx,m;
int my[maxny],mx[maxnx];
int vis[maxnx];
struct edge{
int next,to;
}E[maxm];
int tot=0,head[maxnx];
void addedge(int u,int v){
E[++tot].to=v;
E[tot].next=head[u];
head[u]=tot;
}
int find_path(int u){
if(vis[u])return 0;
vis[u]=1;
vector<int>lj;
for(int i=head[u];i>0;i=E[i].next){
int v=E[i].to;
lj.push_back(v);
}
sort(lj.begin(),lj.end());
for(auto v:lj){
if(my[v]==0||find_path(my[v])){
my[v]=u;
mx[u]=v;
return 1;
}
}
return 0;
}
int a[maxn];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++)
scanf("%d",&a[i]);
for(int i=0;i<=n-1;i++){
int k=a[i];
if(i+k<n)addedge(i+1,i+k+1);
if(i+n-k<n)addedge(i+1,i+n-k+1);
if(i-k>=0)addedge(i+1,i-k+1);
if(i-n+k>=0)addedge(i+1,i-n+k+1);
}
int res=0;
for(int i=n;i>=1;i--){
memset(vis,0,sizeof(vis));
if(find_path(i)){
res++;
}
}
if(res==n){
for(int i=1;i<=n;i++)
printf("%d ",mx[i]-1);
printf("
");
}
else printf("No Answer
");
}
飞行员配对方案问题
共有n个飞行员，外国飞行员编号为1m，本国飞行员编号为m+1n，每架飞机需要一个本国飞行员和一个外国飞行员。每个外国飞行员只能和一些本国飞行员合作，给出至多n^2个合作关系，问至多能形成几个组合？输出最大组合个数和任意一种组合方案
匈牙利算法的应用，加入左部匹配数组mx即可
#include <bits/stdc++.h>
using namespace std;
const int maxnx=1e3+5;
const int maxny=1e3+5;
const int maxm=2e6+5;
int nx,ny,m;
int my[maxny],mx[maxnx];
int vis[maxnx];
struct edge{
int next,to;
}E[maxm];
int tot=0,head[maxnx];
void addedge(int u,int v){
E[++tot].to=v;
E[tot].next=head[u];
head[u]=tot;
}
int find_path(int u){
if(vis[u])return 0;
vis[u]=1;
for(int i=head[u];i>0;i=E[i].next){
int v=E[i].to;
if(my[v]==0||find_path(my[v])){
my[v]=u;
mx[u]=v;
return 1;
}
}
return 0;
}
int main(){
int nx,ny,m;
cin>>nx>>ny;
int u,v;
while(scanf("%d%d",&u,&v)){
if(u==-1&&v==-1)break;
addedge(u,v);
}
int ans=0;
for(int i=1;i<=nx;i++){
memset(vis,0,sizeof(vis));
if(find_path(i)){
ans++;
}
}
printf("%d
",ans);
for(int i=1;i<=nx;i++){
if(mx[i]){
printf("%d %d
",i,mx[i]);
}
}
}