স্টেবল ম্যারেজ প্রবলেম

Resources:

Algorithm — Stable matching problem implementation using c++

The Stable Marriage Problem and School Choice

Stable Marriage Problem

স্টেবল ম্যারেজ প্রবলেম 

 Shakil Ahmed's video

 

Implementation:

	//https://www.codechef.com/problems/STABLEMP
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 1000005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	const ll mod = 1e9 + 7;
	inline void normal(ll &a) { a %= mod; (a < 0) && (a += mod); }
	inline ll modMul(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a * b) % mod; }
	inline ll modAdd(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a + b) % mod; }
	inline ll modSub(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); a -= b; normal(a); return a; }
	inline ll modPow(ll b, ll p) { ll r = 1; while (p) { if (p & 1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
	inline ll modInverse(ll a) { return modPow(a, mod - 2); }
	inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
	///**
	template < typename F, typename S >
	ostream& operator << ( ostream& os, const pair< F, S > & p ) {
	return os << "(" << p.first << ", " << p.second << ")";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const vector< T > &v ) {
	os << "{";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << *it;
	}
	return os << "}";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const set< T > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin()) os << ", ";
	os << *it;
	}
	return os << "]";
	}
	template < typename F, typename S >
	ostream &operator << ( ostream & os, const map< F, S > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << it -> first << " = " << it -> second ;
	}
	return os << "]";
	}
	#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
	clock_t tStart = clock();
	#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
	void faltu () { cerr << endl; }
	template <typename T>
	void faltu( T a[], int n ) {
	for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
	cerr << endl;
	}
	template <typename T, typename ... hello>
	void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
	// Program showing a policy-based data structure.
	#include <ext/pb_ds/assoc_container.hpp> // Common file
	#include <ext/pb_ds/tree_policy.hpp>
	#include <functional> // for less
	#include <iostream>
	using namespace __gnu_pbds;
	using namespace std;
	// GNU link : https://goo.gl/WVDL6g
	typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update>
	new_data_set;
	// find_by_order(k) – ফাংশনটি kth ordered element এর একটা পয়েন্টার রিটার্ন করে। অর্থাৎ তুমি চাইলেই kth ইন্ডেক্সে কি আছে, সেটা জেনে ফেলতে পারছো!
	// order_of_key(x) – ফাংশনটি x এলিমেন্টটা কোন পজিশনে আছে সেটা বলে দেয়।
	//*//**___________________________________________________**/
	vector<int> stableMariage(const vector<vector<int> > &menPf, const vector<vector<int> > &womenPf)
	{
	const int N = menPf.size();
	vector<vector<int>> mapWomenToMan(N);
	for (int i = 0; i < N; i++) mapWomenToMan[i].resize(N);
	for (int i = 0; i < N; i++)
	for (int j = 0; j < N; j++)
	mapWomenToMan[i][womenPf[i][j]] = j;
	vector<int> womenMatch(N, -1);
	vector<int> manMatch(N, -1);
	queue<int> bachelors;
	for (int i = 0; i < N; i++) bachelors.push(i);
	while (!bachelors.empty()) {
	int man = bachelors.front();
	bachelors.pop();
	for (int woman : menPf[man]) {
	if (womenMatch[woman] == -1) { /// women is free
	womenMatch[woman] = man;
	manMatch[man] = woman;
	break;
	}
	else {
	int otherMan = womenMatch[woman];
	if (mapWomenToMan[woman][otherMan] > mapWomenToMan[woman][man]) {
	manMatch[otherMan] = -1;// free the other man
	bachelors.push(otherMan);
	womenMatch[woman] = man;
	manMatch[man] = woman;
	break;
	}
	}
	}
	}
	return manMatch;
	}
	int main()
	{
	//FASTIO
	///*
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	scanf("%d", &T);
	//T = 1;
	for (int cs = 1; cs <= T; cs++) {
	int n; scanf("%d", &n);
	vector<vector<int> > menPf(n), womenPf(n);
	for (int i = 0; i < n; i++) {
	womenPf[i].resize(n);
	int x;
	scanf("%d", &x);
	for (int j = 0; j < n; j++) {
	scanf("%d", &womenPf[i][j]);
	womenPf[i][j]--;
	}
	}
	for (int i = 0; i < n; i++) {
	menPf[i].resize(n);
	int x;
	scanf("%d", &x);
	for (int j = 0; j < n; j++) {
	scanf("%d", &menPf[i][j]);
	menPf[i][j]--;
	}
	}
	vector<int> marriages = stableMariage(menPf, womenPf);
	for (int i = 0; i < n; i++) {
	printf("%d %d\n", i + 1, marriages[i] + 1);
	}
	}
	return 0;
	}

view raw STABLEMP.cpp hosted with ❤ by GitHub

	// 2nd solution
	#include <bits/stdc++.h>
	using namespace std;
	#define INF 1<<30
	#define endl '\n'
	#define maxn 1000005
	#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	typedef long long ll;
	const double PI = acos(-1.0);
	const ll mod = 1e9 + 7;
	inline void normal(ll &a) { a %= mod; (a < 0) && (a += mod); }
	inline ll modMul(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a * b) % mod; }
	inline ll modAdd(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); return (a + b) % mod; }
	inline ll modSub(ll a, ll b) { a %= mod, b %= mod; normal(a), normal(b); a -= b; normal(a); return a; }
	inline ll modPow(ll b, ll p) { ll r = 1; while (p) { if (p & 1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
	inline ll modInverse(ll a) { return modPow(a, mod - 2); }
	inline ll modDiv(ll a, ll b) { return modMul(a, modInverse(b)); }
	///**
	template < typename F, typename S >
	ostream& operator << ( ostream& os, const pair< F, S > & p ) {
	return os << "(" << p.first << ", " << p.second << ")";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const vector< T > &v ) {
	os << "{";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << *it;
	}
	return os << "}";
	}
	template < typename T >
	ostream &operator << ( ostream & os, const set< T > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin()) os << ", ";
	os << *it;
	}
	return os << "]";
	}
	template < typename F, typename S >
	ostream &operator << ( ostream & os, const map< F, S > &v ) {
	os << "[";
	for (auto it = v.begin(); it != v.end(); ++it) {
	if ( it != v.begin() ) os << ", ";
	os << it -> first << " = " << it -> second ;
	}
	return os << "]";
	}
	#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
	clock_t tStart = clock();
	#define timeStamp dbg("Execution Time: ", (double)(clock() - tStart)/CLOCKS_PER_SEC)
	void faltu () { cerr << endl; }
	template <typename T>
	void faltu( T a[], int n ) {
	for (int i = 0; i < n; ++i) cerr << a[i] << ' ';
	cerr << endl;
	}
	template <typename T, typename ... hello>
	void faltu( T arg, const hello &... rest) { cerr << arg << ' '; faltu(rest...); }
	// Program showing a policy-based data structure.
	#include <ext/pb_ds/assoc_container.hpp> // Common file
	#include <ext/pb_ds/tree_policy.hpp>
	#include <functional> // for less
	#include <iostream>
	using namespace __gnu_pbds;
	using namespace std;
	// GNU link : https://goo.gl/WVDL6g
	typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
	tree_order_statistics_node_update>
	new_data_set;
	// find_by_order(k) – ফাংশনটি kth ordered element এর একটা পয়েন্টার রিটার্ন করে। অর্থাৎ তুমি চাইলেই kth ইন্ডেক্সে কি আছে, সেটা জেনে ফেলতে পারছো!
	// order_of_key(x) – ফাংশনটি x এলিমেন্টটা কোন পজিশনে আছে সেটা বলে দেয়।
	//*//**___________________________________________________**/
	const int N = 505;
	int pw[N][N], pm[N][N];
	int cw[N], cm[N];
	void find_wife(int p)
	{
	if (p == 0) return;
	cm[p]++;
	while (1) {
	int w = pm[p][cm[p]];
	if (cw[w] == 0 || pw[w][p] < pw[w][cw[w]]) {
	int h = cw[w];
	cw[w] = p;
	find_wife(h);
	return;
	}
	cm[p]++;
	}
	}
	int main()
	{
	//FASTIO
	///*
	#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("error.txt", "w", stderr);
	#endif
	//*/
	int T;
	scanf("%d", &T);
	//T = 1;
	for (int cs = 1; cs <= T; cs++) {
	int n;
	scanf("%d", &n);
	memset(pw, 0, sizeof pw);
	memset(pm, 0, sizeof pm);
	memset(cw, 0, sizeof cw);
	memset(cm, 0, sizeof cm);
	for (int i = 1; i <= n; i++) {
	int p;
	scanf("%d", &p);
	for (int j = 1; j <= n; j++) {
	int x;
	scanf("%d", &x);
	pw[p][x] = j;
	}
	}
	for (int i = 1; i <= n; i++) {
	int p;
	scanf("%d", &p);
	for (int j = 1; j <= n; j++) {
	int x;
	scanf("%d", &x);
	pm[p][j] = x;
	}
	find_wife(p);
	}
	for (int i = 1; i <= n; i++) {
	//cout << i << " " << pm[i][cm[i]] << "\n";
	printf("%d %d\n", i, pm[i][cm[i]]);
	}
	}
	return 0;
	}

view raw STABLEMP1.cpp hosted with ❤ by GitHub

Problems:

STABLEMP

1400 - Employment

STABLEMP-spoj

/BLOCKING 

11119 - Chemical Attraction 

Share: