Stable Marriage

Stable Matching :

Stable marriage simply works on preference like seeking a better opportunities of matching ,

Finding out best choice from many choice can be done with stable marriage ,the working algorithm is

Gale Shapley Algorithm

in youtube,there are many videos,one of them is

https://www.youtube.com/watch?v=Qcv1IqHWAzg

There are some problems on this

One of them Codechef

 

+View Code

/*
Prog : Stable Marriage
User : Avijeet
Lang : C++
*/
const int N=505;
#include<bits/stdc++.h>
int pos[N][N],wP[N][N],mP[N][N],up[N],out[N];
using namespace std;
int main()
{
int i,j,w,m,t;
queue <int > mfree;

cin>>t;
while(t–)
{
int n;
cin>>n;

for(i=1;i<=n;i++) { cin>>w;
for(j=1;j<=n;j++) cin>>wP[w][j];

}
for(i=1;i<=n;i++) { cin>>m;
for(j=1;j<=n;j++) cin>>mP[m][j];

}

for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
pos[i][wP[i][j]]=j;
//position of man in PL of each woman
//pos[w][m]=i if wP[w][i]=m
memset(out,0,(n+1)*sizeof(int));

for(i=1;i<=n;i++)
{
mfree.push(i);
up[i]=1;
}

while(!mfree.empty())
{
m=mfree.front();
w=mP[m][up[m]++];

if(out[w]==0)
{
out[w]=m;
mfree.pop();

}
else if(pos[w][m]<pos[w][out[w]])
{
mfree.pop();
mfree.push(out[w]);
out[w]=m;
}
}

for(w =1;w<=n;w++)
cout<<out[w]<<” “<<w<<endl;
}
}

 

Advertisements

About waprogramming

I am in CSE,from CUET
This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s