简要题意你课程每个有个时刻可以学习不试题准备rin solution_第1页
简要题意你课程每个有个时刻可以学习不试题准备rin solution_第2页
简要题意你课程每个有个时刻可以学习不试题准备rin solution_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

简要题题目保简要题题目保证存在解简要题本题可以通过构造最大流-最小割模型，将每门课程的分数先最大化，再减去一些不不删的分数，即可得到具体的题首先我们来观察假如没有前置课程，我们该如何来做这1：将每门课分裂成m个时刻，即(i,j)表示i门课的j个时刻，令grade(i,j)表示门课在第j个时刻的分数2：创造一个源点，将源点连向所有(i,1)，流量100-grade(i,1)的边3：对于每门课的第1~m-1个时刻(i,j)向(i,j+1)连一条流量为100-grade(i,j+1)的边4：创造一个汇点，将所有(i,m)连向该汇点，流量为无穷大举一个例n=3,m=3,无前置那么根据上述步骤，构出来的图会变成这经过一次最大流-最小割操作，我们可以得到最大流40，而总学分300-40=260。即为该3107080508020题的最优解那么为什么这题的最优解那么为什么这么构图是对的我们考虑割去一条由(i,j)连向(i,j+1)的边(这里j0，视为源点)，那么就相当于，第i门学科选择了第j+1个课程，而这门课程没有达到满分100分，所以我要删去这条边对应的流而最小割，恰恰满足了，使得源点到汇点不联通时最小因此显而易见，这样做是正确的我们假设学2的前置1。那么该怎么处理还有一点是，若1j完成，学2则必须j之后完成如果学2割的是(1,i-1)-(1,i)这一条边，且i<=j，那么我们可以通过一种方法，使得从源点经处理完了这两种情况，再在上面的图中添加对应的边就还是上面那个例子，假如123的前置课程，那么构出来的图为再举一个有前置课程的例子n=3,m=3,存在两个前置课程，123的前置课程那么我们构出3310508090804

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论