NOIP2014结束之后,这个博客荒废了有一段时间了,今天重新捡起来。就先从网络流开始吧。
题目大意:
给尽可能多的飞机配备2名飞行员，1名来自A组，一名来自B组。(给出AB两组之间的配对关系)。
模型分析:
1.很明显这是一个二分图的最大匹配问题,可以直接用匈牙利算法解决。
2.题目的限制条件只有2个:一个是每个飞行员只能用一次,另外一个是只有能配对的飞行员才能上一架飞机。也就是说每个节点的最大流量为1，且只有能配对的节点直接才能连一条边。最大流的模型就出来了。
构图方法：
1.增加源点S和汇点T。
2.从S到所有A组的点连一条边，容量为1。
3.从所有B组的点到T连一条边，容量为1。
4.对于能配对的Ai,Bj,从Ai到Bj连一条边,容量为1。
总结:
1.熟练了dinic算法,记住了自己容易犯错的地方,比如只有层次相差为1的点之间才能流过去,否则会死递归。我之前以为分层次只是可以加快速度,但实际上层次数组d还起到了vis数组的作用。
2.比较了二分图匹配用匈牙利算法和用网络流算法的效率,虽然dinic算法的复杂度明显要高,但实际上反而运行速度要快一些。