网络流建模思路

一个医院有 n名医生，现有 k个公共假期需要安排医生值班。每一个公共假期由若干天（假日）组成，第 j个假期包含的假日用 Dj表示，那么需要排班的总假日集合为.... 。例如，“五一”假期由5月1日至5月7日一共7个假日组成。“元旦”假期由1月1日至1月3日一共3个假日组成。

每名医生 可以值班的假日集合是 Si,Si属于D，。例如，李医生可以值班的假日集合包括“五一”假期中的5月3日、5月4日和“元旦”假期中的1月2日。

设计一个排班的方案使得每个假日都有一个医生值班并且满足下面两个条件：

1.每个医生最多只能值班c个假日；
2.每个医生在一个假期中只能值班1个假日。例如，安排李医生在“五一”假期中的5月4日值班。

1.构建超级源点 S,和超级汇点T
2.从 S出发构造n条边，指向{ S1, S2...... Sn}这个点集,{ S1, S2,.... Sn}代表n个医生，因为每个医生最多值c个假日，所以这n条边容量为c
3.将{ S1, S2, S3..... Sn}这个点集的每个点i都构造k个边指向{Di1,Di2,Di3....Dik}这个点集，{Di1,Di2,Di3....Dik}代表属于第i个医生的k个假期，因为每个医生在每个假期最多值1天，所以这n * k条边的容量为1
4.构造一个点集{Pi1,Pi2,Pi3,....Pij},表示第i个假期的j个假日。并将{{P11,P12,P13,....P1j},{P21,P22,P23,....P2j},...........{Pk1,Pk2,Pk3,....Pkj}}指向超级汇点T，因为每个假日只分配一个人，所以这些边容量为1
5.若第a个医生可以被分派到第b个假期的第d天，则构造Dab指向Pbd的边，容量为1。因为每个医生最多在某个假日工作一天，所以容量为1
在这里插入图片描述