信息学-解题报告_第1页
信息学-解题报告_第2页
全文预览已结束

下载本文档

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

文档简介

Star解题报贪玩程度；can[i,j]=1,0表示第i个动物会或不会第j项技能。）枚举确定一个动物star。如果发现某个p满足can[star,p]=0，则须想方设法的它第p个技能。由于只考虑一个老师教一个学生，所以教学过程必然是：a1教a2,a2教a3,……,ak-1ak，akstar，简单的表示为a1a2a3……akstar（其中can[a1,p]=1，ai与ai+1互相认识，k为教学场次）也就是求一条以star为终点的路径。另外题目要求教学总时间最短，即最短将每个动物看作一个点，如果xy认识，连两条有向边：1、xy，权为play[x]/teach[y]，表示y教x所花费时间。2、yx，权为play[y]/teach[x]，表示x教y所花费时间。接着以star为源，求单源最短路，在所can[x,p]=1的x中取一个最小的即可。然后找到从x到star对应的最短路，依次教学即可。对每个满足can[star,p]=0的技能p均如此操作，即可得到一组可行解 1、y教x，x教star2、z教x，x但是很容易发现xstar两次！这是毫无意义也毫无必要的。于是我 学。譬如上例就是：yx，zx，xstar。这样就能尽可能的避免根本没有通过分析一，得到求最短路的一个修正方案：求完一条最短路后，顶点都作为源点（star的地位等价。最后求得所有的最短路后，将被标记的响？譬如：m=6，x教y；其中x会的技能是(011001)，y会的的技能是(000001)。这样x能教给y的技能就是{2,3}。假设存在一个z，他会的技能包括{2,3}z和x一起教y，合是S；若存在z，满足z的技能集合包含S，就可以让z和x一同教y。 假设求得的最短路径是A教X，B教X2、CB同教XC和BACX，X可学会{2}；B再单独教X，X可学会{3}AC可以合并起来一起教本来A能单独X{2,3}，而和C合起来教就只能教{2}这一项了，看起来似乎对结果造成了影响啊！但是请注意，{3}这一项技能完全可以由B这位老师来负责，A根本无需操心！实际上A所能教给X的两项技能{2,3}中，只有{2}是它独有的，称之为一般的来说，X教YX能教给Y的技能集合记为S，X能教给Y、但是其他老师不能教给Y的技能记为S’。那么显然有S’包含于S。若存在一个Z，Z会的技能集合包含了S’（不必包含S），则Z就有资格和X一起教Y。1、枚举一个动物star作为2star不会

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

温馨提示

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

最新文档

评论

0/150

提交评论