稳定婚配系统）"/>
hdu 1914 The Stable Marriage Problem（稳定婚配系统）
关于稳定婚配，下面的博客写得很错，思路很好理解
.html
模板
View Code#include <iostream>
using namespace std;
const int MAX = 4;
int main()
{
int libMan[MAX][MAX] = {{2, 1, 3, 0}, {0, 2, 3, 1}, {2, 3, 1, 0}, {1, 3, 2, 0}}; //存储男士所喜欢的女士序号的排列表
int libLady[MAX][MAX+1] = {{0, 3, 1, 2, MAX}, {1, 3, 2, 3, MAX}, {0, 2, 3, 1, MAX}, {1, 0, 3, 2, MAX}}; //存储女士所喜欢的男士序号的排列表
int libladyValue[MAX][MAX+1] = {0};
for (int i = 0; i < MAX; i++) //把女士喜好的男士序号的排列表转换为男士分值表
{
for (int j = MAX, k = 0; j >= 0; j--, k++)
{
libladyValue[i][libLady[i][j]] = k;
}
}
int man[MAX+1] = {0};//存储各个男士追求女士的次数
int lady[MAX] = {MAX, MAX, MAX, MAX}; //序号初始值MAX表示一个“不存在”的男士，即其分值比任何男士都低
int S[MAX] = {0};//一个栈，用来存储所有自由男的序号
int top = 0;
while (top < MAX) //把所有自由男的序号存储到栈中
S[top] = top++;
top--; //top指向栈顶
while (top >= 0)//让自由男主动去追求自己喜欢的女士，直到所有的人都配对
{
int v = libMan[S[top]][man[S[top]]]; //处在栈顶（序号为S[top]）的男士喜欢v号女
if (libladyValue[v][lady[v]] < libladyValue[v][S[top]]) //若栈顶男比v号女当前男友优秀，则 v抛弃前男友，接受栈顶男
{
int t = lady[v]; //存储前男友序号
man[t]++; //抛弃前男友，即前男友选择其“次喜欢女”
lady[v] = S[top--]; //选择栈顶男为新男友，同时栈顶男出栈
if (t != MAX) //如果t号男不是那个“不存在”的男士
S[++top] = t; //t号男作为新的栈顶男
}
else //栈顶男追求下一号目标
man[S[top]]++;
}
for (int i = 0; i < MAX; i++) //输出每位男士追求女士的次数
cout << man[i] + 1 << ", ";
cout << endl;
for (int i = 0; i < MAX; i++) //输出每位男士的妻子的序号
cout << libMan[i][man[i]] << ", ";
cout << endl;
for (int i = 0; i < MAX; i++) //输出每位女士的丈夫的序号
cout << lady[i] << ", ";
cout << endl;
return 0;
}
稳定婚配的模板题
下面的倆道题目都是赤裸裸的模板题
hdu1914 The Stable Marriage Problem
View Code#include<iostream>
using namespace std;
const int MAX = 27;
int libMan[MAX][MAX],libLady[MAX][MAX+1],libladyValue[MAX][MAX+1];
int man[MAX+1],lady[MAX];
int hashm[MAX],hashf[MAX];
bool ism[MAX],isf[MAX];
void solve(int n)
{
int s[MAX]={0},top;
memset(man,0,sizeof(man));
for(int i=0;i<n;i++)
{
lady[i]=n;
s[i]=i;
}
top=n-1;
while(top>=0)
{
int v=libMan[s[top]][man[s[top]]];
if(libladyValue[v][lady[v]]<libladyValue[v][s[top]])
{
int t=lady[v];
man[t]++;
lady[v]=s[top--];
if(t!=n)
s[++top]=t;
}
else man[s[top]]++;
}
}
int main()
{
int T,cas=0,n;
char name[MAX];
scanf("%d",&T);
while(T--)
{
memset(ism,false,sizeof(ism));
memset(isf,false,sizeof(isf));
if(cas)
puts("");
cas++;
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",name);
ism[name[0]-'a']=true;
}
for(int i=0;i<n;i++)
{
scanf("%s",name);
isf[name[0]-'A']=true;
}
int m=0,f=0;
for(int i=0;i<MAX;i++)
{
if(ism[i])
hashm[i]=m++;
if(isf[i])
hashf[i]=f++;
}
for(int i=0;i<n;i++)
{
scanf("%s",name);
int mm=hashm[name[0]-'a'];
for(int j=2;j<n+2;j++)
libMan[mm][j-2]=hashf[name[j]-'A'];
}
for(int i=0;i<n;i++)
{
scanf("%s",name);
int ff=hashf[name[0]-'A'];
for(int j=2;j<n+2;j++)
libLady[ff][j-2]=hashm[name[j]-'a'];
libLady[ff][n]=n;
}
for(int i=0;i<n;i++)
for(int j=n,k=0;j>=0;j--,k++)
libladyValue[i][libLady[i][j]]=k;
solve(n);
for(int i=0;i<MAX;i++)
{
if(ism[i])
printf("%c %c\n",i+'a',libMan[hashm[i]][man[hashm[i]]]+'A');
}
}
return 0;
}
hdu1435 Stable Match
View Code#include<iostream>
#include<algorithm>
#include<math.h>
const int MAX = 210;
using namespace std;
struct node
{
double x,y,z,w;
int id;
};
struct dist
{
double d,w;
int id;
dist(){}
dist(int id,double d,double w):id(id),d(d),w(w){}
};
node send[MAX],rec[MAX];
dist dis[MAX];
double gg[MAX][MAX];
int n,ss[MAX][MAX],rr[MAX][MAX],s[MAX],r[MAX];
int rv[MAX][MAX];
double get_dis(node a,node b)
{
gg[a.id][b.id]=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)+(a.z-b.z)*(a.z-b.z);
return gg[a.id][b.id];
}
bool cmp(dist a,dist b)
{
if(a.d!=b.d)
return a.d<b.d;
return a.w>b.w;
}
void init()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
dis[j]=dist(rec[j].id,get_dis(send[i],rec[j]),rec[j].w);
sort(dis+1,dis+n+1,cmp);
for(int j=1;j<=n;j++)
ss[send[i].id][j]=dis[j].id;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
dis[j]=dist(send[j].id,get_dis(rec[i],send[j]),send[j].w);
sort(dis+1,dis+n+1,cmp);
for(int j=1,k=n;j<=n;j++,k--)
{
rr[rec[i].id][j]=dis[j].id;
rv[rec[i].id][dis[j].id]=k;
}
rv[rec[i].id][n+1]=0;
}
for(int i=1;i<=n;i++)
{
r[i]=n+1;
s[i]=1;
}
}
void solve()
{
int st[MAX];
for(int i=1;i<=n;i++)
{
st[i-1]=send[i].id;
}
int top=n-1;
while(top>=0)
{
int v=ss[st[top]][s[st[top]]];
if(rv[v][r[v]]<rv[v][st[top]])
{
int t=r[v];
s[t]++;
r[v]=st[top--];
if(t!=n+1)
st[++top]=t;
}
else s[st[top]]++;
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d %lf %lf %lf %lf",&send[i].id,&send[i].w,&send[i].x,&send[i].y,&send[i].z);
for(int i=1;i<=n;i++)
scanf("%d %lf %lf %lf %lf",&rec[i].id,&rec[i].w,&rec[i].x,&rec[i].y,&rec[i].z);
init();
solve();
for(int i=1;i<=n;i++)
printf("%d %d\n",r[i],i);
printf("\n");
}
return 0;
}
hdu1522 Marriage is Stable
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;const int N = 500+10;int libMan[N][N],libLady[N][N],libladyValue[N][N];
int man[N],lady[N],n;
map<string,int> men,women;
char name1[N][50],name2[N][50],str[50];void solve()
{int s[N]={0},top=0;memset(man,0,sizeof(man));for(int i=0;i<n;++i){lady[i]=n;s[i]=i;}top=n-1;while(top>=0){int v=libMan[s[top]][man[s[top]]];if(libladyValue[v][lady[v]]<libladyValue[v][s[top]]){int t=lady[v];man[t]++;lady[v]=s[top--];if(t!=n)s[++top]=t;}else man[s[top]]++;}
}
int main()
{while(scanf("%d",&n)==1){scanf("%s",name1[0]);men.clear();women.clear();men[string(name1[0])]=0;for(int j=0;j<n;++j){scanf("%s",name2[j]);women[string(name2[j])]=j;libMan[0][j]=j;}for(int i=1;i<n;++i){scanf("%s",name1[i]);men[string(name1[i])]=i;for(int j=0;j<n;++j){scanf("%s",str);libMan[i][j]=women[string(str)];}}for(int i=0;i<n;++i){scanf("%s",str);int id=women[string(str)];for(int j=0;j<n;++j){scanf("%s",str);libLady[id][j]=men[string(str)];}libLady[id][n]=n;}for(int i=0;i<n;++i)for(int j=n,k=0;j>=0;j--,++k)libladyValue[i][libLady[i][j]]=k;solve();for(int i=0;i<n;++i)printf("%s %s\n",name1[i],name2[libMan[i][man[i]]]);puts("");}return 0;
}
转载于:.html
更多推荐
hdu 1914 The Stable Marriage Problem（稳定婚配系统）
发布评论