Description

Input

Output

　　仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。

Sample Input

　　3 2

　　10 0

　　20 0

　　-10 0

　　-5 1 0 0

　　100 1 2 1

　　100 0

Sample Output

　　25

 

---

 

Solution

　　按照依赖关系建立有向图：若清除$a$前必须清除$b$，则连边$a$至$b$。这些依赖关系包括同行植物左边对右边的依赖，以及被保护者对保护者的依赖。

　　首先不能考虑开挂集团，也就是依赖关系成强联通分量的植物，也包括能通过依赖关系走到强联通分量的植物——它们都无敌，需要排除掉。这可以用tarjan加上反向边的深搜预处理。

　　

　　一个植物能够下手，当且仅当其出度为0.

　　每一株植物又是带正负权值的，那么明显是要在依赖图中，求一个最大权闭合子图。也就是要有植物起手（迎合闭合的性质，出边都在闭合子图内，即依赖的植物都要一起干掉，都应该在闭合子图的范围内），且干掉的植物权值和最大。

　　按照最大权闭合子图的建立方法：源点向所有正权点连容量为其权值的边，所有负权点向汇点连容量为其权值绝对值的边；所有节点按依赖关系连边，容量为$+\infty$。

　　答案是所有正权点点权值和减去最大流。能将负权转化为正权来跑网络流的原因，拆拆括号就可以发现，这是很巧妙的。

---

#include 
      
       #include 
       
        #include 
        
         using namespace std;const int N=610,INF=2147000000;int n,m,a[N],h[N],hr[N],tot;int dfn[N],low[N],tmcnt,is[N],st[N],top,ins[N],vis[N];int S,T,dis[N],cur[N];int sum;queue
         
           q;vector
          
            list[N];struct Edge{
    int v,f,next;}g[1000010];inline int min(int x,int y){
    return x
           
            =0){ addEdge(S,x,a[x]); sum+=a[x]; } else addEdge(x,T,-a[x]); int sz=list[x].size(); for(int k=0;k