Stable Match

稳定婚姻问题

主要就是处理两个数组

boy[i][j]    存放第i个男的第j喜欢的女的   存的是女的编号!!

girl[i][j]   存放 第i个女的对第j个男的的好感度  存的是值

然后只要模板就行了

这题的数据处理有点麻烦  多学习！

#include<bits/stdc++.h>

using namespace std;

#define N 1000

int rank1[N];

int match_boy[N],match_girl[N];

double boy[N][N],girl[N][N];

int n;

struct node

{

    int cap,idx;

    double x,y,z;

}lau[N],acc[N];

struct ode

{

    int idx,cap;

    double len;

}aim[N];

bool cmp(ode a,ode b)

{

    if(  fabs(a.len-b.len)<0.000001 )return a.cap>b.cap;

    else return a.len<b.len;

}

int main()

{

    int cas;cin>>cas;

    while(cas--)

    {

        scanf("%d",&n);

        for(int i=;i<=n;i++)

           scanf("%d %d %lf %lf %lf",&lau[i].idx,&lau[i].cap,&lau[i].x,&lau[i].y,&lau[i].z);

        for(int i=;i<=n;i++)

           scanf("%d %d %lf %lf %lf",&acc[i].idx,&acc[i].cap,&acc[i].x,&acc[i].y,&acc[i].z);

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=n;j++)

           {

             aim[j].len = sqrt((lau[i].x-acc[j].x)*(lau[i].x-acc[j].x) + (lau[i].y-acc[j].y)*(lau[i].y-acc[j].y) + (lau[i].z-acc[j].z)*(lau[i].z-acc[j].z));

             aim[j].cap = acc[j].cap;

             aim[j].idx = acc[j].idx;

           }

             sort(aim+,aim++n,cmp);//求第i个男的对所有的女的好感排序

             for(int j=;j<=n;j++)

                boy[i][j]=aim[j].idx;//放置第i个男的第j喜欢的女的是谁！

        }

        for(int i=;i<=n;i++)

        {

            for(int j=;j<=n;j++)

           {

            aim[j].len = sqrt((acc[i].x-lau[j].x)*(acc[i].x-lau[j].x) + (acc[i].y-lau[j].y)*(acc[i].y-lau[j].y) + (acc[i].z-lau[j].z)*(acc[i].z-lau[j].z));

            aim[j].cap = lau[j].cap;

            aim[j].idx = lau[j].idx;

           }

          sort(aim+,aim++n,cmp);

          for(int j=;j<=n;j++)

            girl[ acc[i].idx ][ aim[j].idx ]=n-j;//放置第i个女的对第j个男的的好感度！ 不需要放len  直接n-j就行

        }

        //处理好boy和girl数组    其他的完全一样！

        int flag=;

        memset(match_boy,,sizeof match_boy);

        memset(match_girl,,sizeof match_girl);

        memset(rank1,,sizeof rank1);

        while(flag)

        {

            flag=;

            for(int i=;i<=n;i++)

            {

                if(!match_boy[i])

                {

                    int temp=boy[i][rank1[i]++];

                    if(!match_girl[temp])

                      match_boy[i]=temp,match_girl[temp]=i;

                     else if( girl[temp][i]>girl[temp][match_girl[temp]] )

                       {

                           match_boy[ match_girl[temp] ]=;

                            match_boy[i]=temp;

                            match_girl[temp]=i;

                       }

                       flag=;

                }

            }

        }

    for(int i=;i<=n;i++)

                cout<<i<<' '<<match_boy[i]<<endl;

                cout<<endl;

    }

    return ;

}