第一次把 $\text{OI}$ 知识运用到实际里去！

前言

高三的时候了解到雅礼有一个传统的活动叫“情系雅礼蓝”，大概是上一届的学长学姐为高三的学弟学妹组织了一系列活动啥的。

其中有一项内容是一对一匹配高校的学长学姐和高三的学弟学妹进行书信交流。高三的时候因为比较摆（？），而且有点迷茫和焦虑，所以我非常积极地参加了这个活动，并且找到了在 $\text{THU}$ 的一位我很小的时候就认识的学姐进行了交流 当时还询问了如何学化学之类的问题 虽然最后化学还是学成了依托

上大学之后和一位同学一起接下了这一届的雅礼蓝任务，并对书信交流活动进行了一些不知道是优化还是劣化的改动。

方案描述

去年的形式是给高三的每个班级分配 $x$ 个某大学的书信名额，有需要的话班级之间调换，并一次性直接写信过去。我们认为可能存在这样的问题：

  1. 不同班级的积极性不同，且名额分配很难做到公平公正（例如竞赛班的清北名额肯定是最多的）；
  2. 直接写信过去，回信的人并不确定，这也限制了写信者可写的内容。

于是我们捏出了这样一套新的方案：

首先，发放“申请表”，上面有所有大学可供的名额数量，每位同学可以选择三个“志愿”，并简述自己想要了解的问题。

接下来，由我们收集“申请表”并进行名额分配，完成了高三学弟学妹 & 高校 & 学长学姐的对应之后，再发放信纸进行书信交流。

这个方法有这样一些优势：

  1. “志愿”的填写由学生自行决定，避免了名额分配不均，或班级之间大幅度交换名额等问题；
  2. 学生在写信的时候已经明确了收信方，于是写信内容可以更有针对性；
  3. 看起来更公平，可能甩给我们的锅比较少。

确定方案之后，接下来最关键的步骤就是如何分配名额了。

名额分配的具体方式

名额分配分为两步：学弟学妹 $\to$ 高校 $\to$ 学长学姐。

当学弟学妹已经分配到高校之后，只需要将申请表统一发到该学校，并让学长学姐自行认领即可。于是我们只需要讨论第一个步骤的实现方式。

方案 1：人工

在申请表的信息录入之前，设想的方案只需要人工操作，按照志愿顺序直接分配，人数过多就随机选择一下啥的。

后来看到申请表全貌之后，发现存在以下问题：

  1. 一些大学非常火爆 好像不包括华子，直接按上述方法操作可能导致一些人三个志愿都选不上；
  2. 方案比较“鼠目寸光”，或导致一些大学分不到名额，一些大学过载，可能会打击学长学姐的积极性；
  3. 方案确定后如果要进行适当修改，工作量会很大；
  4. 要靠人来做，好累。

方案 2：费用流

容易从中抽象出一个匹配问题的模型。只需要定义如何给一个方案计算收益，就可以使用最大费用最大流来求出全局最优解了。

目前设置了以下参数：

  1. 一位学生（是否学生会？）选中第一/第二/第三志愿的收益；
  2. 一个大学多收到一张申请表的收益（用于避免一个大学收到的申请表太少）；
  3. 一个大学如果“过载”，需要扣除的收益。

于是容易求出在某固定参数下的全局最优解。

方案 2 存在的问题

经过一些玄学调参，我发现了如下问题：

  1. “第一志愿”的重要性难以凸显；
  2. 靠后志愿的差异可能直接导致结果的不同：例如两个人只有第三志愿不同，那么第三志愿冷门的人会被直接分配到第三志愿，这是明显不合理的；
  3. 如何分配参数之间的大小关系，数量级之间应该满足什么公式。

目前还没想到咋解决 让雅礼蓝的朋友们一起手动改改得了（，如果居然真的有人能看到这篇文章，也欢迎大家在评论区帮俺想想处理方法/kel

标签: 费用流

添加新评论