8 、 图论—匹配

8.1 二分图最大匹配(hungary 邻接表)

//二分图最大匹配,hungary 算法,邻接表形式,复杂度 O(m*e)
//返回最大匹配数,传入二分图大小 m,n 和邻接表 list(只需一边)
//match1,match2 返回一个最大匹配,未匹配顶点 match 值为-1
#include <string.h>
#define MAXN 310
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
struct edge_t{
int from,to;
edge_t* next;
};
int hungary(int m,int n,edge_t* list[],int* match1,int* match2){
int s[MAXN],t[MAXN],p,q,ret=0,i,j,k;edge_t* e;
for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (e=list[k=s[p]];e&&match1[i]<0;e=e->next)
if (t[j=e->to]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
return ret;
}

8.2 二分图最大匹配(hungary 邻接阵)

//二分图最大匹配,hungary 算法,邻接阵形式,复杂度 O(m*m*n)
//返回最大匹配数,传入二分图大小 m,n 和邻接阵 mat,非零元素表示有边
//match1,match2 返回一个最大匹配,未匹配顶点 match 值为-1
#include <string.h>
#define MAXN 310
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
int hungary(int m,int n,int mat[][MAXN],int* match1,int* match2){
int s[MAXN],t[MAXN],p,q,ret=0,i,j,k;
for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (k=s[p],j=0;j<n&&match1[i]<0;j++)
if (mat[k][j]&&t[j]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
return ret;
}

8.3 二分图最大匹配(hungary 正向表

//二分图最大匹配,hungary 算法,正向表形式,复杂度 O(m*e)
//返回最大匹配数,传入二分图大小 m,n 和正向表 list,buf(只需一边)
//match1,match2 返回一个最大匹配,未匹配顶点 match 值为-1
#include <string.h>
#define MAXN 310
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
int hungary(int m,int n,int* list,int* buf,int* match1,int* match2){
int s[MAXN],t[MAXN],p,q,ret=0,i,j,k,l;
for (_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (l=list[k=s[p]];l<list[k+1]&&match1[i]<0;l++)
if (t[j=buf[l]]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
return ret;
}

8.4 二分图最佳匹配(kuhn_munkras 邻接阵)

//二分图最佳匹配,kuhn munkras 算法,邻接阵形式,复杂度 O(m*m*n)
//返回最佳匹配值,传入二分图大小 m,n 和邻接阵 mat,表示权值
//match1,match2 返回一个最佳匹配,未匹配顶点 match 值为-1
//一定注意 m<=n,否则循环无法终止
//最小权匹配可将权值取相反数
#include <string.h>
#define MAXN 310
#define inf 1000000000
#define _clr(x) memset(x,0xff,sizeof(int)*n)
int kuhn_munkras(int m,int n,int mat[][MAXN],int* match1,int* match2){
int s[MAXN],t[MAXN],l1[MAXN],l2[MAXN],p,q,ret=0,i,j,k;
for (i=0;i<m;i++)
for (l1[i]=-inf,j=0;j<n;j++)
l1[i]=mat[i][j]>l1[i]?mat[i][j]:l1[i];
for (i=0;i<n;l2[i++]=0);
for (_clr(match1),_clr(match2),i=0;i<m;i++){
for (_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
for (k=s[p],j=0;j<n&&match1[i]<0;j++)
if (l1[k]+l2[j]==mat[k][j]&&t[j]<0){
s[++q]=match2[j],t[j]=k;
if (s[q]<0)
for (p=j;p>=0;j=p)
match2[j]=k=t[j],p=match1[k],match1[k]=j;
}
if (match1[i]<0){
for (i--,p=inf,k=0;k<=q;k++)
for (j=0;j<n;j++)
if (t[j]<0&&l1[s[k]]+l2[j]-mat[s[k]][j]<p)
p=l1[s[k]]+l2[j]-mat[s[k]][j];
for (j=0;j<n;l2[j]+=t[j]<0?0:p,j++);
for (k=0;k<=q;l1[s[k++]]-=p);
}
}
for (i=0;i<m;i++)
ret+=mat[i][match1[i]];
return ret;
}

8.5 一般图匹配( 邻接表)

//一般图最大匹配,邻接表形式,复杂度 O(n*e)
//返回匹配顶点对数,match 返回匹配,未匹配顶点 match 值为-1
//传入图的顶点数 n 和邻接表 list
#define MAXN 100
struct edge_t{
int from,to;
edge_t* next;
};
int aug(int n,edge_t* list[],int* match,int* v,int now){
int t,ret=0;edge_t* e;
v[now]=1;
for (e=list[now];e;e=e->next)
if (!v[t=e->to]){
if (match[t]<0)
match[now]=t,match[t]=now,ret=1;
else{
v[t]=1;
if (aug(n,list,match,v,match[t]))
match[now]=t,match[t]=now,ret=1;
v[t]=0;
}
if (ret)
break;
}
v[now]=0;
return ret;
}
int graph_match(int n,edge_t* list[],int* match){
int v[MAXN],i,j;
for (i=0;i<n;i++)
v[i]=0,match[i]=-1;
for (i=0,j=n;i<n&&j>=2;)
if (match[i]<0&&aug(n,list,match,v,i))
i=0,j-=2;
else
i++;
for (i=j=0;i<n;i++)
j+=(match[i]>=0);
return j/2;
}

8.6 一般图匹配( 邻接阵)

//一般图最大匹配,邻接阵形式,复杂度 O(n^3)
//返回匹配顶点对数,match 返回匹配,未匹配顶点 match 值为-1
//传入图的顶点数 n 和邻接阵 mat
#define MAXN 100
int aug(int n,int mat[][MAXN],int* match,int* v,int now){
int i,ret=0;
v[now]=1;
for (i=0;i<n;i++)
if (!v[i]&&mat[now][i]){
if (match[i]<0)
match[now]=i,match[i]=now,ret=1;
else{
v[i]=1;
if (aug(n,mat,match,v,match[i]))
match[now]=i,match[i]=now,ret=1;
v[i]=0;
}
if (ret)
break;
}
v[now]=0;
return ret;
}
int graph_match(int n,int mat[][MAXN],int* match){
int v[MAXN],i,j;
for (i=0;i<n;i++)
v[i]=0,match[i]=-1;
for (i=0,j=n;i<n&&j>=2;)
if (match[i]<0&&aug(n,mat,match,v,i))
i=0,j-=2;
else
i++;
for (i=j=0;i<n;i++)
j+=(match[i]>=0);
return j/2;
}

8.7 一般图匹配(正向表)

//一般图最大匹配,正向表形式,复杂度 O(n*e)
//返回匹配顶点对数,match 返回匹配,未匹配顶点 match 值为-1
//传入图的顶点数 n 和正向表 list,buf
#define MAXN 100
int aug(int n,int* list,int* buf,int* match,int* v,int now){
int i,t,ret=0;
v[now]=1;
for (i=list[now];i<list[now+1];i++)
if (!v[t=buf[i]]){
if (match[t]<0)
match[now]=t,match[t]=now,ret=1;
else{
v[t]=1;
if (aug(n,list,buf,match,v,match[t]))
match[now]=t,match[t]=now,ret=1;
v[t]=0;
}
if (ret)
break;
}
v[now]=0;
return ret;
}
int graph_match(int n,int* list,int* buf,int* match){
int v[MAXN],i,j;
for (i=0;i<n;i++)
v[i]=0,match[i]=-1;
for (i=0,j=n;i<n&&j>=2;)
if (match[i]<0&&aug(n,list,buf,match,v,i))
i=0,j-=2;
else
i++;
for (i=j=0;i<n;i++)
j+=(match[i]>=0);
return j/2;
}