稳定婚姻匹配
HDOJ 1435 Stable Match(此例基于发射点优先的匹配，但题目并未明确表明)
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1236 Accepted Submission(s): 583
Special Judge
Problem Description
Network 公司的BOSS 说现在他们公司建立的信号发射站和接收站经常出现信号发送接收不稳定的问题,信号的稳定度被定义为发射点到接收点的距离,距离越大,越不稳定,所以发射点跟接收点在可能的情况下应越近越好.
BOSS给8600的任务就是：:建立一个匹配表,使得一个发射点对应一个接收点,对于某一个发射点来说,它的接收点离它越近那么就会更稳定,同样对于接收点也是一样的情况. 匹配的目标是使得整个网络变得稳定。,对于某2个匹配,比如,( a ---- 1) ,(b----2) ,如果发射点a 离接收点2 比 1要近,而且2 也离 发射点a要比 b 近, 那么 a 就很有可能把信号发到 2中,我们就说这个搭配是不 稳定的。同样如果发射点b 离接收点1 比 2 要近,而且1 也离 发射点b要比 a 近 ,也会出现不稳定的情 况. 而且每个点都有一个容量值,如果对于一个发射点到2个接收点的距离一样的话,它将首先选择容量大的那个. 所以8600就是要建立一个稳定的匹配,使得每个一个信号发射点对应一个接收点,并且不会出现信号不稳定的情况.
8600苦思冥想也没什么进展,希望你能帮他解决这个难题.
Input
输入数据首先包含一个正整数N,N<=20表示测试实例的个数.每个实例首先是一个整C,C<=200表示有C个信号发射点和C个信号接收点. 接下来的C行表示 C个发射点的编号,容量和坐标,坐标为,x,y,z 3个实数(x,y,z ≥0).最后C行是C个接收点的编号,容量和坐标.
Output
输出建立稳定搭配后各个发射点和接收点的编号,每一行代表一个搭配,前一个整数为发射点的编号，后一个为对应的接收点的编号。如果有多种情况，输出其中一种即可.如果任务不可能完成的话,输出"Impossible".每个实例后请输出一个空行.
Sample Input
1
3
1 1 60.57 57.16 69.27
2 2 26.05 61.06 11.52
3 3 9.04 58.20 56.90
1 2 280.74 12.78 316.14
2 3 305.16 267.15 87.65
3 1 240.72 312.41 217.10
Sample Output
3 1
1 2
2 3
想法
这是一个稳定婚姻问题，稳定婚姻问题就是n个男的和n个女的结婚，然后目的是为了让婚姻关系更稳定，在每一个男人的心中有一个排列：n个女人在自己心中的喜爱程度。每一个女人心中对每一个男人都有一个评分。例如a-b，c-d是两对夫妻，但是a更喜欢d多一点与此同时c又更满意b，那么显然会有人出轨，这样就是不稳定的关系，现在寻求一种方法使得婚姻关系变得稳定，这就需要用到一种方法：男生询问女生，女生比较男生。具体一点来说就是，在男生的心里有一个女生的排名，那么男生按照这个排名去寻找女生，那么如果这个女生没有匹配任何男生，那么这个女的就会和这个男的在一起，如果这个女生已经匹配到了男生，那么就需要将这个男生和已经和女生匹配的那个男生进行比较看看女生更喜欢谁，如果原来的男生被淘汰了，那么直接扔回队列即可，其实这种方式找下来是对男生有利的，因为男生找到的女的都是合理情况下最喜欢的女生。
本题输出时按照接收点的顺序输出
#include "bits/stdc++.h"
using namespace std;
int C;
struct Node{
double w, x, y, z;
Node(double w=0, double x=0, double y=0, double z=0):w(w),x(x),y(y),z(z) {}
}A[201], B[201]; //分别用来存放发射点和接收点的数据
struct P{
int to;
double w, d;
bool operator < (const P &rhs) const {
if(d==rhs.d) return w>rhs.w;
return d<rhs.d;
}
P(int a=0, double b=0, double c=0):to(a),w(b),d(c) {}
}; //用于所有的接收点在每一个发射点中的排序
bool vis[201]; //接收点是否已经匹配
int pr[201]; //接收点所匹配的发射点
P lj[201][201]; //用于排序的邻接矩阵
inline double dis(int a, int b) {
return sqrt((A[a].x-B[b].x)*(A[a].x-B[b].x)+(A[a].y-B[b].y)*(A[a].y-B[b].y)+(A[a].z-B[b].z)*(A[a].z-B[b].z));
} //求发射点与接收点距离的函数
void presolve() { //输入及预处理
memset(vis,0,sizeof(vis));
cin>>C;
for(int i=0; i<C; ++i) {
int a;
double w, x, y, z;
cin>>a>>w>>x>>y>>z;
A[a-1]=Node(w,x,y,z); //把所有的点的编号-1， 输出时+1
}
for(int i=0; i<C; ++i) {
int a;
double w, x, y, z;
cin>>a>>w>>x>>y>>z;
B[a-1]=Node(w,x,y,z);
}
for(int i=0; i<C; ++i) {
for(int j=0; j<C; ++j) {
lj[i][j]=P(j,B[j].w,dis(i,j)); //求所有发射点与所有接收点的距离
}
}
for(int i=0; i<C; ++i) sort(lj[i],lj[i]+C); //把接收点进行排序
}
inline bool cmp(int a, int b, int v) {
if((dis(a,v)<dis(b,v))||(dis(a,v)==dis(b,v)&&A[a].w>A[b].w)) return 1;
return 0;
} //用于比较是否发射点a比发射点b更适合接收点v
int main() {
int N;
cin>>N;
while(N--) {
presolve();
queue<int> q;
for(int i=0; i<C; ++i) q.push(i); //先把所有的发射点放进队列
int f;
while(q.size()) {
int now=q.front(); q.pop();
f=0;
for(int i=0; i<C; ++i) {
int v=lj[now][i].to;
if(!vis[v]) { //如果接收点还未匹配
vis[v]=1, pr[v]=now, f=1;
break;
}
else if(vis[v]&&cmp(now,pr[v],v)) { //如果接收点已经匹配但是now比之前的匹配点pr[v]更适合
q.push(pr[v]);
pr[v]=now;
f=1;
break;
}
}
if(!f) break; //如果一个发射点now无法与任何一个接收点匹配，则表明Impossible
}
if(!f) printf("Impossible\n\n");
else {
for(int i=0; i<C; ++i) printf("%d %d\n", pr[i]+1, i+1); //输入时-1，勿忘输出时+1
puts("");
}
}
}
HDOJ 1914 The Stable Marriage Problem(此例基于男性优先，题目明确表明)
The Stable Marriage Problem
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1334 Accepted Submission(s): 628
Problem Description
The stable marriage problem consists of matching members of two different sets according to the member’s preferences for the other set’s members. The input for our problem consists of:
a set M of n males;
a set F of n females;
for each male and female we have a list of all the members of the opposite gender in order of preference (from the most preferable to the least).
A marriage is a one-to-one mapping between males and females. A marriage is called stable, if there is no pair (m, f) such that f ∈ F prefers m ∈ M to her current partner and m prefers f over his current partner. The stable marriage A is called male-optimal if there is no other stable marriage B, where any male matches a female he prefers more than the one assigned in A.(这句话表明优先让男性满意)
Given preferable lists of males and females, you must find the male-optimal stable marriage.
Input
The first line gives you the number of tests. The first line of each test case contains integer n (0 < n < 27). Next line describes n male and n female names. Male name is a lowercase letter, female name is an upper-case letter. Then go n lines, that describe preferable lists for males. Next n lines describe preferable lists for females.
Output
For each test case find and print the pairs of the stable marriage, which is male-optimal. The pairs in each test case must be printed in lexicographical order of their male names as shown in sample output. Output an empty line between test cases.
Sample Input
2
3
a b c A B C
a:BAC
b:BAC
c:ACB
A:acb
B:bac
C:cab
3
a b c A B C
a:ABC
b:ABC
c:BCA
A:bac
B:acb
C:abc
Sample Output
a A
b B
c C
a B
b A
c C
以下代码是基于HDOJ 1522 Marriage is Stable作的小改动而得到的AC码，因此保留了map(也可采用 字母-'a’或字母-'A’的方式)
#include "bits/stdc++.h"
using namespace std;
int n;
char l;
map<char,int> cg11, cg12;
map<int,char> cg21, cg22;
int boy[27][27], gl[27][27];
int link[27], link1[27]; //前者为女性的匹配，后者为要输出的男性的匹配
char hh[27];
int main() {
ios::sync_with_stdio(false);
int T;
cin>>T;
while(T--) {
cin>>n;
cg11.clear(), cg12.clear(), cg21.clear(), cg22.clear();
for(int i=0; i<n; ++i) cin>>hh[i]; //将男性名字记录下来
sort(hh,hh+n); //按字典序排序
for(int i=0; i<n; ++i) {
cg11[hh[i]]=i, cg21[i]=hh[i]; //给男性名字按字典序编号0，1，2，···
}
for(int i=0; i<n; ++i) {
cin>>l;
cg12[l]=i, cg22[i]=l; //给女性名字编号，按读入顺序编号即可
}
for(int i=0; i<n; ++i) {
cin>>l;
int a=cg11[l];
cin>>l;
for(int j=0; j<n; ++j) {
cin>>l;
boy[a][j]=cg12[l]; //按男性对女性的喜欢程度依次放进去
}
}
for(int i=0; i<n; ++i) {
cin>>l;
int a=cg12[l];
cin>>l;
for(int j=0; j<n; ++j) {
cin>>l;
gl[a][cg11[l]]=j; //注意：此处与上面不同，因为要用于比较某一女性对两个男性的喜欢程度，因此保存这位女性对某位男性的喜欢程度排名
}
}
queue<int> q;
for(int i=0; i<n; ++i) q.push(i); //将男性按顺序放进去，以下为正常的稳定匹配代码
memset(link,-1,sizeof(link));
memset(link1,-1,sizeof(link1));
while(q.size()) {
int now=q.front(); q.pop();
for(int i=0; i<n; ++i) {
int v=boy[now][i];
if(link[v]==-1) {
link[v]=now;
link1[now]=v;
break;
}
else if(gl[v][now]<gl[v][link[v]]) {
q.push(link[v]);
link[v]=now;
link1[now]=v;
break;
}
}
}
for(int i=0; i<n; ++i) {
cout<<cg21[i]<<" "<<cg22[link1[i]]<<endl;
}
if(T) cout<<endl;
}
}
![查找算法之二分查找查找算法之二分查找[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)