首页 > 其他 > 详细

专题训练5总结

时间:2019-02-17 20:05:42      阅读:296      评论:0      收藏:0      [点我收藏+]

这个专题学习了两种算法 

1.稳定婚姻匹配问题

2.最大团问题

稳定婚姻匹配问题:

1.Stable Match

关于信号站匹配

多了一个容量的权值  如果距离相同看容量大小

数据处理较麻烦!

 

2.marriage

稳定婚姻匹配问题入门题

 

3.The Stable Marriage problem

和入门题没啥区别 不说了

 

4.University Entrace Examination

稳定婚姻匹配问题的变形!

数据很杂

 

总之  复习时重做1,4题

 

最大团问题:

1.Maximum Clique

最大团入门  套用模板

 

2.maximum shortest distance

在n个点中取k个点  使k个点中距离最短的点最大

采用二分答案做法!!结合最大团

很值得学习 

有关最大团的进一步理解

 

3.Channel Allocation

染色问题  相邻不能染同一种颜色

很像高中的数学排列组合问题

染色问题可直接套用最大团模板

颜色数==最大团定点数

如果超过四个肯定是哪里有问题了   四色原则

 

4.All Friends

极大团问题  去套极大团数量模板!

 

5.Graph Coloring

最大团和最大独立集团的问题    

这题是求最大独立集团的点的个数和位置

可以用最大团的补图  再用模板

 

总结 : 除了两个模板题都看看

 

专题训练5总结

原文:https://www.cnblogs.com/bxd123/p/10392311.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!