<题目链接>
题目大意：
给你n个发射站和n个接受站的位置，并且给出他们的容量，现在需要你对这n对站台进行匹配，距离越近的站台越稳定，如果两个站台距离相等，容量越大的越稳定。问你稳定匹配是什么，如果不存在的话，输出 "impposible "。
解题分析：
Gale_Shapley的模板题，我们只需要分别预处理一下每个发射站对应接收站的优先级，以及每个接收站的所有发射站的优先度即可。需要注意的是，婚姻匹配问题一定有解，所以不用考虑无解的情况。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
using namespace std; #define N 205
#define clr(a,b) memset(a,b,sizeof(a))
#define srep(i,s,t) for(int i=s;i<t;i++) struct point {
int num,col;
double x,y,z;
}arr1[N],arr2[N]; struct Node {
int num,col;
double dis;
}node[N];
int n;
int linker1[N],linker2[N],vis[N][N],mpa1[N][N],mpa2[N][N]; double calc(point p,point q){
return sqrt((p.x-q.x)*(p.x-q.x)+(p.y-q.y)*(p.y-q.y)+zz*zz);
}
int comp(Node p,Node q){
return p.dis<q.dis || p.dis==q.dis && p.col>q.col;
}
void Gale_Shapley(){
clr(vis,);clr(linker1,-);clr(linker2,-);
queue<int> q;
srep(i,,n) q.push(i);
while (!q.empty()){
int u=q.front(),v;
q.pop();
srep(i,,n){ //遍历该发射站的所有接收站
int v=mpa1[u][i];
if (vis[u][v]) continue;
vis[u][v]=;
if (linker2[v]==-){
linker2[v]=u;
linker1[u]=v;
break; //该发射站找到接受站，直接跳出
}
else if(mpa2[v][linker2[v]]<mpa2[v][u]){ //当前发射站与该接受站的稳定性 优于 该接受站原来匹配的发射站稳定性
q.push(linker2[v]);
linker2[v]=u;
linker1[u]=v;
break;
}
}
}
srep(i,,n) cout << arr1[i].num << " " << arr2[linker1[i]].num << endl;
cout << endl;
}
int main(){
ios::sync_with_stdio(false);
cin.tie();cout.tie();
int T;cin >> T; while(T--){
cin >> n;
srep(i,,n){
cin >> arr1[i].num >> arr1[i].col >> arr1[i].x >> arr1[i].y >> arr1[i].z;
}
srep(i,,n){
cin >> arr2[i].num >> arr2[i].col >> arr2[i].x >> arr2[i].y >> arr2[i].z;
}
//预处理每个接受站对每个发射站的优先级
srep(i,,n){
srep(j,,n){
node[j].dis=calc(arr1[i],arr2[j]);
node[j].col=arr2[j].col;
node[j].num=j;
}
sort(node,node+n,comp);
srep(j,,n) mpa1[i][j]=node[j].num;
}
//预处理每个发射站对每个接受栈的优先度
srep(i,,n){
srep(j,,n){
node[j].dis=calc(arr2[i],arr1[j]);
node[j].col=arr1[j].col;
node[j].num=j;
}
sort(node,node+n,comp);
srep(j,,n) mpa2[i][node[j].num]=n-j+;
}
Gale_Shapley();
}
return ;
}
2019-01-19