題意：

? ? ? ? ? ? ? ?Stable Match

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

思路：
? ? ? 穩定婚姻問題，先說明下，這個題目雖然是中文的，讀了好幾遍才讀懂，還有就是題目沒有敘述全吧，就是應該加上 如果接受者面臨兩個距離一樣的發射者，那么他要選擇權值權值大的發射者，這個沒說，整的我以為發射者的權值沒用呢，后來排序的時候發現會有問題，自己加上去的，還有就是這個題目不存在 Impossible 的情況，因為穩定婚姻問題肯定有解的，然后就是細微的地方，去處理每個接受者在發射者心中的地位，和每個發射者在接受者心中的地位，然后就是穩定婚姻問題了，下面我粘貼下我剛剛寫好的自己對穩定婚姻的理解，本題用到的算法較容易實現，所以我的是我自己手寫的，看著不舒服的可以去網上找找正規模板啥的。


穩定婚姻問題就是給你n個男的，n個女的，然后給你每個男生中女生的排名，和女生心目中男生的排名，然后讓你匹配成n對，使婚姻穩定，假如a和b匹配,c和d匹配，如果a認為d比b好，同時d也認為a比c好，那么ad就有可能私奔，這樣就導致了婚姻的不穩定，穩定婚姻就是找到一種解決方案讓婚姻穩定
算法：
? ? ? 穩定婚姻的解決方法比較簡單，通俗易懂，而且還容易實現，具體有沒有固定的模板我不知道，沒有去找，自己模擬的，在求解的過程中，我們先把所有的男生都加到隊列里，隊列里的就表示當前還單身的男生，每次從隊列里拿出一個男生，然后從她最喜歡的女生開始匹配，如果當前的女生嘗試追求過，那么就不用追求了，如果當前的女生沒有伴侶，那么可以直接匹配上，如果有伴侶，那么就看看當前這個男生和女生之前的伴侶在那個女生中更喜歡誰，如果更喜歡當先的這個男生，那么當前男生就和這個女生匹配，女生之前匹配過的直接變成單身，被扔回隊列，否則，繼續找下一個女生，知道找到一個能匹配上的為止，就這樣一直到隊列空的時候，就已經全部匹配完成了。


正確性：
? ? ? ? 對于男生來說，每次都是從最喜歡的女生開始匹配的，遇到的第一個沒人能搶走的并且穩定的就是自己最終伴侶，也就是說如果之前追求過的女生被別人搶走了，那么他將永遠搶不會來，因為對于女生來說，第一次被男士按照自己的意愿選擇之后，每次變更匹配對象都是在自己心目中更加喜歡的，所以一旦他放棄了某個男生，那么那個男生就沒希望在和他匹配，這樣男生是從最優的選的，保證男生不會出軌，女生每次都是在選擇她的男生中選擇最優的，這樣也保證了女生最后沒有怨言，這樣的話，最后的到的婚姻就是穩定的，至于穩定婚姻，肯定會有穩定方案，這個我暫時證明不了.<1962年，美國數學家 David Gale 和 Lloyd Shapley是這兩個人發明的方法，并且證明了穩定婚姻一定會有解>。

#include<queue> #include<math.h> #include<stdio.h> #include<string.h> #include<algorithm>#define N 200 + 5 using namespace std;typedef struct {int num ,v;double x ,y ,z; }NODE;typedef struct {double dis;int v ,id; }ZT;NODE node1[N] ,node2[N]; ZT zt[N]; int map[N][N] ,G_b[N][N]; int nowb[N] ,nowg[N]; int mark[N][N];bool camp(ZT a ,ZT b) {return a.dis < b.dis || a.dis == b.dis && a.v > b.v; }void Marr(int n) {queue<int>q;for(int i = 1 ;i <= n ;i ++)q.push(i);memset(mark ,0 ,sizeof(mark));memset(nowb ,255 ,sizeof(nowb));memset(nowg ,255 ,sizeof(nowg));while(!q.empty()){int xin ,tou = q.front();q.pop();for(int i = 1 ;i <= n ;i ++){xin = map[tou][i];if(mark[tou][xin]) continue;mark[tou][xin] = 1;if(nowg[xin] == -1){nowg[xin] = tou;nowb[tou] = xin;break;}else{if(G_b[xin][tou] > G_b[xin][nowg[xin]]){q.push(nowg[xin]);nowg[xin] = tou;nowb[tou] = xin;break;}}}}return; }double get_dis(NODE a ,NODE b) {double xx = (a.x - b.x) * (a.x - b.x);double yy = (a.y - b.y) * (a.y - b.y);double zz = (a.z - b.z) * (a.z - b.z);return xx + yy + zz; }int main () {int t ,n ,i ,j;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(i = 1 ;i <= n ;i ++)scanf("%d %d %lf %lf %lf" ,&node1[i].num ,&node1[i].v ,&node1[i].x ,&node1[i].y ,&node1[i].z);for(i = 1 ;i <= n ;i ++)scanf("%d %d %lf %lf %lf" ,&node2[i].num ,&node2[i].v ,&node2[i].x ,&node2[i].y ,&node2[i].z);for(i = 1 ;i <= n ;i ++){for(j = 1 ;j <= n ;j ++){zt[j].dis = get_dis(node1[i] ,node2[j]);zt[j].v = node2[j].v;zt[j].id = j;}sort(zt + 1 ,zt + n + 1 ,camp);for(j = 1 ;j <= n ;j ++)map[i][j] = zt[j].id;}for(i = 1 ;i <= n ;i ++){for(j = 1 ;j <= n ;j ++){zt[j].dis = get_dis(node2[i] ,node1[j]);zt[j].v = node1[j].v;zt[j].id = j;}sort(zt + 1 ,zt + n + 1 ,camp);for(j = 1 ;j <= n ;j ++)G_b[i][zt[j].id] = n - j + 1;}Marr(n);for(i = 1 ;i <= n ;i ++)printf("%d %d\n" ,node1[i].num ,node2[nowb[i]].num);puts("");}return 0; }

總結

以上是生活随笔為你收集整理的hdu1435 稳定婚姻问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。