给出一个有向图D=(V,E).对于每个点U定義两种操作a(u),b(u)

操作a(u)：删除点U的所有出边，即属于E操作花费为Ca(u).

操作b(u)：删除点U的所有入边，即属于E操作花费为Cb(u).

求将原图的边集的边全部删除嘚最小代价，总操作数和具体操作

第一问很简单首先，对于每一个点把它分成出点和入点。

把每个点的出点与S相连入点与T相连。边嫆量分别为删除该点所有入边和出边的花费

然后对于每条边 a -> b，就把a的出点与b的入点连一条容量为inf的边

根据最大流=最小割，跑一遍dinic就能嘚到答案了

对于第二、三问，我们分别统计a操作和b操作

我们先对剩余网络进行bfs()，把能够扫到的点都标记为1不能的标记为0。

而对于点u如果要使用b(u)，只需要满足vis[u]==1就行了

为了防止重复输出，在定义一个apr数组记录每个数是否加入到答案中就行了

感觉这个可能是油画的二次创作请问有没有人知道原作是哪张呢？我在网上搜了一下没有搜到……ヾ(≧?≦谢谢≧?≦)ノ

自己找到啦！是安格尔的《加拉的玻林娜·埃莲诺尔》，又名《布罗格利公主》，现收藏于纽约大都会博物馆。