yifeiwang-ep / mcmf Goto Github PK

我们想要完成一个一键视频编辑合成的功能，为一些服饰类目的商品产出模特展示视频。具体就是我们让用户上传m段视频片段，会通过算法分析，每个视频分割出多段素材片段，总量为k，k >= m。同时预设一个视频模板脚本，包含了n个段落特效的模板。再根据某种算法，我们可以为n个段落，从k个素材片段中，选取出n个作为最优解进行填充，生成出一个剪辑过的视频片段合成内容。

已知，n个段落特效的模板，我们会为每个段落设定好一些特征值，包括该段落坑位设计师认为最优的画面模特主体的位置p，占画面的面积s，是否有脸部特写f，片段最佳时长d等特征。同时上述生成分割素材片段的算法，也已经分析出了素材片段对应上述所说的特征值。

问题：设计一个算法，根据上述给定的k个素材片段和n那个模板段落坑位，以及他们对应的特征值(p,s,f,d)。如何从k个素材中选出最优的n个进行填充。 有不理解没明白的地方，可以追加邮件问一次问题。然后在下周一上午发给我解决的思路、具体的算法、最好带有伪代码或者代码，强制要求Java语言编码风格。

算法：最小费用最大流+欧式距离。 思路：将给出的n个标准四元组，将他们构建n个点，每个点都连一条边到汇点T，容量为1，保证每个四元组最多被选一次。对于k个四元组，构建k个点，从S连边到这些点，容量为1。对于和S相连的k个点，分别连接到另外那n个点，每条边容量为1，费用为匹配值。最大流决定了这n个坑全填, 容量为1决定了这n个坑只会被填一次，这样建图的目的是可以保证最终选n个四元组。最大流可以选出n个片段，最小费用决定选出的n个方案是最优的。 每条边的费用为两个四元组的匹配值，把决定最优这件事，通过judge函数计算，返回值是一个整数，整数越大，越不优。将每个四元组看作四维空间上的一个点，那么两个点之间的距离就是他们的匹配值。