自己写的稳定婚姻匹配模板，测试过，可靠

//婚配问题 by 混沌的云Knight
//传入男人数n，女人数m
//男人对女人好感矩阵mtw，女人对男人好感矩阵wtm，匹配矩阵
//match1，match2 匹配成功返回1，否则返回0
//match1,match2返回一个成功婚姻匹配,未匹配顶点match值为-1
#include<string.h>
#define  MAXN 502
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
char W[MAXN][MAXN];
int _O[MAXN];
int marry(int n,int m,int mtw[][MAXN],int wtm[][MAXN],int *match1,int *match2)
{
    int i=0,j,h,M,t=-1,s1=n,s2=m;
    memset(W,0,sizeof(W));    
    for(_clr(match1),_clr(match2);i<n;_O[++t]=i,i++);
    while(t>=0)
    {
        h=_O[t--];
        for(M=-1,i=0;i<m;i++)
                if(!W[h][i]&&(M==-1||mtw[h][i]>mtw[h][M]))
                    M=i;
        W[h][M]=1;
        if(match2[M]==-1)
        {
            match1[h]=M;
            match2[M]=h;
            s1--;s2--;
        }else if(wtm[M][h]>wtm[M][match2[M]])
        {
            match1[match2[M]]=-1;
            _O[++t]=match2[M];
            match1[h]=M;
            match2[M]=h;
        }else
            _O[++t]=h;
    }
    return (!s1)||(!s2);
}