1497: [NOI2006]最大获利

差点连网络流都写炸了。

看到这题容易想到最大闭合子权图,考虑建图。

从源点连向i一个流量为p[i]的边,

有一个边的时候,新建一个点,由两个端点连向这个点一个无限流量的边,这个点再连向汇点一个流量为价值的边,搞定。

c++代码如下:

 

5 + 4 =