"Проблема больниц / жителей" действительно может сработать, но это зависит от ваших ограничений:
- Больница имеет максимальную вместимость и будет отдавать распоряжение резиденту (наиболее разыскиваемые, менее разыскиваемые).
- Жители будут заказывать больницы.
- Другие ограничения невозможны.
В вашем случае больницы - рабочие, а жители - слоты.
- Слоты могут заказывать работники (может быть, вы предпочитаете экспериментальные по утрам ...).
- Рабочие могут заказать слоты.
- Но у вас не может быть других ограничений, таких как: «Я работал утром, я не хочу работать в тот же день вечером».
Если это нормально для вас, тогда у вас есть возможности:
Вы хотите дать преимущество работникам: «больничный кейс».
Вы попытаетесь назначить работников на их предпочтительные слоты.
вы хотите воспользоваться слотами: «резидентно-ориентированный кейс»
Каждый слот будет иметь своих предпочитаемых работников.
Я должен был закодировать его в прошлом году, вот код.
/*
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;
}
}
}
Пример использования, чтобы показать, как построить ранг из префов.
(В этом случае списки предпочтений были на stdin).
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_pref:
- 1 -> 2 5 6 1 (предпочитает 2, затем 5, затем 6, затем 1)
- 2 -> 4 2 1 6 3 5
- 3 -> 1 2
R_pref:
- 1 -> 1 2 3
- 2 -> 3 1
- 3 -> 2 1
- 4 -> 1 3 2
- 5 -> 3 2 1
- 6 -> 3
H_rank:
- 1 -> 4 1 INF INF 2 3 (1 находится в позиции 4 в H_pref [1], 3 не три)
- 2 -> 3 2 5 1 6 4
- 3 -> 1 2 INF INF INF INF INF
Аналогично для R_rank.
Больница не должна оценивать всех и может также оценивать меньше людей, чем их возможности.