HDU 1435 Stable Match 【稳定婚姻问题】

题目大意：
给你n个发射站和n个接受站的位置，并且给出他们的容量，现在需要你对这n对站台进行匹配，距离越近的站台越稳定，如果两个站台距离相等，容量越大的越稳定。问你稳定匹配是什么，如果不存在的话，输出 "impposible "。

解题分析：

Gale_Shapley的模板题，我们只需要分别预处理一下每个发射站对应接收站的优先级，以及每个接收站的所有发射站的优先度即可。需要注意的是，婚姻匹配问题一定有解，所以不用考虑无解的情况。

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cmath>
 5 #include<queue>
 6 using namespace std;
 7 
 8 #define N 205
 9 #define clr(a,b) memset(a,b,sizeof(a))
10 #define srep(i,s,t) for(int i=s;i<t;i++)
11 
12 struct point {
13     int num,col;
14     double x,y,z;
15 }arr1[N],arr2[N];
16 
17 struct Node {
18     int num,col;
19     double dis;
20 }node[N];
21 int n;
22 int linker1[N],linker2[N],vis[N][N],mpa1[N][N],mpa2[N][N];
23 
24 double calc(point p,point q){
25     return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)+zz*zz);
26 }
27 int comp(Node p,Node q){
28     return p.dis<q.dis || p.dis==q.dis && p.col>q.col;
29 }
30 void Gale_Shapley(){
31     clr(vis,0);clr(linker1,-1);clr(linker2,-1);
32     queue<int> q;
33     srep(i,0,n) q.push(i);
34     while (!q.empty()){
35         int u=q.front(),v;
36         q.pop();
37         srep(i,0,n){       //遍历该发射站的所有接收站
38             int v=mpa1[u][i];
39             if (vis[u][v]) continue;
40             vis[u][v]=1;
41             if (linker2[v]==-1){
42                 linker2[v]=u;
43                 linker1[u]=v;
44                 break;            //该发射站找到接受站，直接跳出
45             }
46             else if(mpa2[v][linker2[v]]<mpa2[v][u]){       //当前发射站与该接受站的稳定性 优于 该接受站原来匹配的发射站稳定性
47                 q.push(linker2[v]);
48                 linker2[v]=u;
49                 linker1[u]=v;
50                 break;
51             }
52         }
53     }
54     srep(i,0,n) cout << arr1[i].num << " " << arr2[linker1[i]].num << endl;
55     cout << endl;
56 }
57 int main(){
58     ios::sync_with_stdio(false);
59     cin.tie(0);cout.tie(0);
60     int T;cin >> T; while(T--){
61         cin >> n;
62         srep(i,0,n){
63             cin >> arr1[i].num >> arr1[i].col >> arr1[i].x >> arr1[i].y >> arr1[i].z;
64         }
65         srep(i,0,n){
66             cin >> arr2[i].num >> arr2[i].col >> arr2[i].x >> arr2[i].y >> arr2[i].z;
67         }
68         //预处理每个接受站对每个发射站的优先级
69         srep(i,0,n){
70             srep(j,0,n){
71                 node[j].dis=calc(arr1[i],arr2[j]);
72                 node[j].col=arr2[j].col;
73                 node[j].num=j;
74             }
75             sort(node,node+n,comp);
76             srep(j,0,n) mpa1[i][j]=node[j].num;
77         }
78         //预处理每个发射站对每个接受栈的优先度
79         srep(i,0,n){
80             srep(j,0,n){
81                 node[j].dis=calc(arr2[i],arr1[j]);
82                 node[j].col=arr1[j].col;
83                 node[j].num=j;
84             }
85             sort(node,node+n,comp);
86             srep(j,0,n) mpa2[i][node[j].num]=n-j+1;
87         } 
88         Gale_Shapley();
89     }
90     return 0;
91 }

2019-01-19