?? 一般圖匹配(鄰接陣形式).txt
字號:
//一般圖最大匹配,鄰接陣形式,復雜度O(n^3)
//返回匹配頂點對數(shù),match返回匹配,未匹配頂點match值為-1
//傳入圖的頂點數(shù)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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -