“医院/居民问题”确实可以解决，但这取决于你的限制：
- 医院有最大容量，并将命令住院医师（最想要的到不太想要的）。
- 居民将订购医院。
- 不可能有其他限制。
在你的例子中，医院是工人，居民是槽位。
- 老虎机可以命令工人（也许你更喜欢在早上进行实验......）。
- 工人可以订购槽位。
- 但你不能有其他限制，例如：“我早上工作，我不想在晚上工作”。
如果这对你来说没问题，那么你就有可能：
-
您想为工人提供优势：“以医院为导向的案例”。
您将尝试将工作人员分配到他们喜欢的位置。
-
您想要优势槽位：“面向居民的案例”
每个槽位都会有自己喜欢的工人。
我去年必须编写它，这是代码。
/*
RO : needed for Resident-Oriented version
HO : needed for Hospital-Oriented version
*/
const int MAX_R = 1000;
const int MAX_H = 1000;
const int INF = 1000*1000*1000;
您需要填写输入变量。
一切都很简单：
- R_pref 和 H_pref 是居民/医院的偏好列表
- H_rank[h][r] 是 r 在 H_pref[h] 中的排名：r 在 h 的偏好列表中的位置
就这样。
// Input data
int R, H; // Number of Residents/Hospitals
int C[MAX_H]; // Capacity of hospitals
vector<int> R_pref[MAX_R], H_pref[MAX_H]; // Preferences : adjency lists
/*RO*/int H_rank[MAX_H][MAX_R]; // Rank : rank of r in H_pref[h]
/*HO*/int R_rank[MAX_R][MAX_H]; // Rank : rank of h in R_pref[r]
下面不用碰。
// Internal data
int RankWorst[MAX_H]; // Rank of the worst r taken by h
/*RO*/int BestH[MAX_R]; // Indice of the best h in R_pref the r can get
/*HO*/int BestR[MAX_H]; // Indice of the best r in H_pref the h can get
int Size[MAX_H]; // Number of residents taken by h
// Output data
int M[MAX_R];
void stable_hospitals_RO()
{
for(int h = 0 ; h < H ; h++)
RankWorst[h] = H_pref[h].size()-1;
fill_n(BestH, R, 0);
fill_n(Size, H,0);
fill_n(M,R,INF);
for (int i = 0; i < R; i++)
for (int r = i; r >= 0;)
{
if(BestH[r] == int(R_pref[r].size()))
break;
const int h = R_pref[r][BestH[r]++];
if(Size[h]++ < C[h])
{
M[r] = h;
break;
}
int WorstR = H_pref[h][RankWorst[h]];
while(WorstR == INF || M[WorstR] != h) // Compute the worst
WorstR = H_pref[h][--RankWorst[h]];
if(H_rank[h][r] < RankWorst[h]) // Ranked better that worst
{
M[r] = h;
M[r = WorstR] = INF; // We have eliminate it, he need to put it somewhere
}
}
}
void stable_hospitals_HO()
{
fill_n(BestR, H, 0);
fill_n(Size, H,0);
fill_n(M,R,INF);
vector<int> SH;
for (int h = 0; h < H; h++)
SH.push_back(h);
while(!SH.empty())
{
int h = SH.back();
if(Size[h] == C[h] || BestR[h] == int(H_pref[h].size())) // Full or no r available
{
SH.pop_back();
break;
}
const int r = H_pref[h][BestR[h]++];
// r is unassigned or prefer h to current hospital
if(M[r] == INF || R_rank[r][h] < R_rank[r][M[r]])
{
if(++Size[h] == C[h]) // Will be full
SH.pop_back();
if(M[r] != INF) // Delete from M[r]
{
Size[M[r]]--;
SH.push_back(M[r]);
}
M[r] = h;
}
}
}
用于展示如何根据首选项建立排名的示例。
（在这种情况下，首选项列表位于标准输入上）。
int main()
{
scanf("%d%d",&R,&H);
int num;
// put inf
for(int r = 0 ; r < R ; r++)
{
scanf("%d",&num);
R_pref[r].resize(num);
for(int h = 0 ; h < num ; h++)
{
scanf("%d",&R_pref[r][h]);
R_rank[r][R_pref[r][h]] = h;
}
}
for(int h = 0 ; h < H ; h++)
{
scanf("%d",&C[h]);
scanf("%d",&num);
H_pref[h].resize(num);
for(int r = 0 ; r < num ; r++)
{
scanf("%d",&H_pref[h][r]);
H_rank[h][H_pref[h][r]] = r;
}
}
stable_hospitals_RO();
printf("\n\n\n\n");
stable_hospitals_HO();
return 0;
}
举个例子：
1 号至 3 号医院，6 名居民。
H_首选项：
- 1 -> 2 5 6 1（优先选择 2 然后 5 然后 6 然后 1）
- 2 -> 4 2 1 6 3 5
- 3 -> 1 2
R_首选项：
- 1 -> 1 2 3
- 2 -> 3 1
- 3 -> 2 1
- 4 -> 1 3 2
- 5 -> 3 2 1
- 6 -> 3
H_等级：
- 1 -> 4 1 INF INF 2 3 （1 位于 H_pref[1] 中的位置 4，3 不存在）
- 2 -> 3 2 5 1 6 4
- 3 -> 1 2 INF INF INF INF
R_rank 类似。
医院不必对每个人进行排名，也可以对少于其容量的人进行排名。
