Skip to content

shady831213/codeM2018

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

10 Commits
 
 
 
 
 
 
 
 

Repository files navigation

资格赛第5和第6题

以每个站的48个时间为图的顶点。每个站的出站时间连接到下一站的所有比到站时间晚的时间点。

反向dfs找到所有valid的路径。

这个节点去掉时间最晚的那条边。

单源最短路径算结果。

先排序再用二分图最大匹配找最大匹配。

xMatch和yMatch要保存下来。如果新添加的边没有产生节点增加,即x的点或者y的点的个数小于i+1,则一定不会形成新的最大匹配,这时继续添加新的边,直到两边节点的个数都达到了i+1,计算最大匹配。如果存在最大匹配,一定是新加进来的这些边造成的,因为边被从小到大排序,这时最先形成最大匹配的边即为此时的瓶颈边。

特殊情况:

  • 假如所有的左节点都连接到一个右节点,或者反之,此时会遍历所有的边。对于这种情况,在排序时记下左点和右点的个数,如果i+1超过min([x],[y]),则之后一定不会形成最大匹配。
  • 假如每次都增加一个新的匹配,则最多计算n次,且每次hk都只需要计算一个增广路径。

另外:

  • 排序的选择:用堆排可以在读取数据时完成排序
  • 用slice要比map性能高很多
  • 优化io
  • 本地最大数据平均500ms+,但是提交上去时间将将过,不知道是不是还有什么没考虑的情况。。。。

About

Part of codeM2018 AC solutions

Resources

License

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages