题面 传送门:洛谷 Solution 这道题,需要一个小技巧了解决。 我相信很多像我这样接蒟蒻，看到这道题，不禁兴奋起来：“这道题是裸的割边，我会做！！！” 然后兴冲冲的打了个DINIC，交一发，80分。 所以说我们有时候还是太naive。 重新读题，会发现这题割的不是边，是点。这样还能80分，数据真水 所以说，我们需要一个割边转割点的小技巧。 我们可以考虑“拆点”，即把一个点拆成两个点，中间连一条边权为1的边。 前一个点作为“入点”，别的点连边连入这里。 后一个点作为“出点”，出去的边从这里出去。 这样，只要我们…
传送门：洛谷 Solution 网络流 先引用一句真理:网络流最重要的就是建模 今天这道题让我深有体会 首先,观察数据范围,n=100,一般这种100-1000的图论题,很有可能是网络流. 那就直接从网络流的角度入手 考虑这样建模 建模要点如下: 1.建权值为1的边,保证每个食物和水仅用一次 2.没了 对以上的图求一个最大流,那不就是我们想要的最大的匹配数吗? 看起来是不是很OjbK? . 其实不然,这样子一头牛有可能脚踏N条食物和水,但是题目要求一头牛只能吃喝一次 反例如下: 所以说,我们要对一头牛吃的东西做一个…
最近评论
hilaolu 发布于 4 个月前（03月16日）
Guava 发布于 8 个月前（11月30日）
碱式碳酸希 发布于 8 个月前（11月30日）
碱式碳酸希 发布于 9 个月前（11月04日）
630分苦苦挣扎的菜鸡土豆 发布于 1 年前（05月01日）