图论

Maximum Weight Closure of a Graph

今天做题遇到了这个经典问题,拜读了《最小割模型在信息学竞赛中的应用》也顺便回顾下网络流的相关知识。全文当作是对论文的回顾,同时感谢作者的辛勤付出。

Introduction

最大权闭合图指的是一个有向图$G=(V,E)$的点集$V$,且该点集满足如果$u$在$V$中,那么$u$指向的后继$v$也在$V$中,给每个点分配一个权值(可正可负),那么最大的权闭合子图就是点权最大的闭合图。 (更多…)

luoyayu