match.cpp

回溯法 解决男女匹配问题 八男八女匹配

#include "stdio.h"
#include "iostream"
#define N  8


//static int MR[N+1][N+1];
//static int WR[N+1][N+1];
static int MW[N+1][N+1];
static int WM[N+1][N+1];
static int X[N+1];
static int Y[N+1];
static bool single[N+1];
static int MR[N+1][N+1]={
                    {0,0,0,0,0,0,0,0,0},
                    {0,7,2,6,5,1,3,8,4},
                    {0,4,3,2,6,8,1,7,5},
                    {0,3,2,4,1,8,5,7,6},
                    {0,3,8,4,2,5,6,7,1},
                    {0,8,3,4,5,6,1,7,2},
                    {0,8,7,5,2,4,3,1,6},
                    {0,2,4,6,3,1,7,5,8},
                    {0,6,1,4,2,7,5,3,8}
    };	
static int WR[N+1][N+1]={
                    {0,0,0,0,0,0,0,0,0},
                    {0,4,6,2,5,8,1,3,7},
                    {0,8,5,3,1,6,7,4,2},
                    {0,6,8,1,2,3,4,7,5},
                    {0,3,2,4,7,6,8,5,1},
                    {0,6,3,1,4,5,7,2,8},
                    {0,2,1,3,8,7,4,6,5},
                    {0,3,5,7,2,4,1,8,6},
                    {0,7,2,8,4,5,6,3,1}
    };

////////////////////////////////////////////////////////////////////////////////
//判断是否匹配
bool stable(int m,int w,int r){
    //判断男子是否稳定
    int pm,pw;
    bool sta=true;
    int L,i=1;
    while(i<r&&sta){
        pw=MR[m][i];
        i++;
        if(!single[pw]){
            if(WM[pw][m]>WM[pw][Y[pw]]){
                sta=true;
            }
            else sta=false;
        }
    }
    if(!sta){return sta;}
    //判断女子是否稳定
    i=1;
    L=WM[w][m] ;
    while(i<L){
        pm=WR[w][i];
        i++;
        if(pm<m){
            if(MW[pm][w]>MW[pm][X[pm]]){
                sta=true;
            }
            else sta=false;
        }
    }
    return sta;
}

////////////////////////////////////////////////////////////////////////////////
//进行分配
bool tryMatch(int m){
    int r=0;
    int w;
    bool q1=false;
    while(r<=N&&!q1){
        r++;
        w=MR[m][r];
        if(single[w]){
            if(stable(m,w,r)){
                X[m]=w;
                Y[w]=m;
                single[w]=false;
                if(m<N){
                    q1=tryMatch(m+1);
                    if(!q1){
                        single[w]=true;
                    }
                }
                else q1=true;
            }
        }
    }
    return q1;
}

////////////////////////////////////////////////////////////////////////////////
//打印结果
void Print(){
    int m,rm=0,rw=0;
    for(m=1;m<=N;m++){
        printf(" (%d,%d) ",m,X[m]);
        rm=rm+MW[m][X[m]];
        rw=rw+WM[X[m]][m];
    }
    printf("\n men: %d    women:%d  \n",rm,rw);
}

void main(){
    int i=0,j=0,k=0;
    bool success=false;
    for(i=0;i<=N;i++){
        single[i]=true;
    }

    for(i=0;i<=N;i++){
        for(j=0;j<=N;j++){
            MW[i][j]=0;
            WM[i][j]=0;
        }
    }
    for(i=1;i<=N;i++){
        for(j=1;j<=N;j++){
            k=MR[i][j];
            MW[i][k]=j;
            k=WR[i][j];
            WM[i][k]=j;
        }
    }
   /////////////////////////////////////////////////////////////////////////////


   success=tryMatch(1);
   if(success){
        Print();
   }
   else printf("\n No Solution! ");

}