原文地址：http://www.cnblogs.com/GXZlegend/p/6808268.html
题目描述
输入
输出
仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。
样例输入
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0
样例输出
25
题解
拓扑排序+最大权闭合图
一个坑点卡了半年。。
由题目描述易知如果某些植物保护关系成了环，那它们都不能吃掉。所以若A能保护B，则A向B连边，再用拓扑排序判环（Tarjan也可以）。
注意如果A在B的前边，那么也应看作A保护B。
然后所有被无敌植物保护的植物都不能吃掉，应用dfs判掉。
最后跑最大权闭合图即可。
坑点有点多，实际没啥太难的。
#include <cstdio>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;
queue<int> q;
int n , m , map[610][610] , w[610] , rd[610] , flag[610];
int head[610] , to[400000] , val[400000] , next[400000] , cnt = 1 , s , t , dis[610];
void init()
{
int i , j;
for(i = 1 ; i <= n * m ; i ++ )
for(j = 1 ; j <= n * m ; j ++ )
if(map[i][j])
rd[j] ++ ;
for(i = 1 ; i <= n * m ; i ++ )
if(!rd[i])
q.push(i);
while(!q.empty())
{
i = q.front() , q.pop() , flag[i] = 1;
for(j = 1 ; j <= n * m ; j ++ )
{
if(map[i][j])
{
rd[j] -- ;
if(!rd[j]) q.push(j);
}
}
}
}
void add(int x , int y , int z)
{
to[++cnt] = y , val[cnt] = z , next[cnt] = head[x] , head[x] = cnt;
to[++cnt] = x , val[cnt] = 0 , next[cnt] = head[y] , head[y] = cnt;
}
bool bfs()
{
int x , i;
while(!q.empty()) q.pop();
memset(dis , 0 , sizeof(dis));
dis[s] = 1 , q.push(s);
while(!q.empty())
{
x = q.front() , q.pop();
for(i = head[x] ; i ; i = next[i])
{
if(val[i] && !dis[to[i]])
{
dis[to[i]] = dis[x] + 1;
if(to[i] == t) return 1;
q.push(to[i]);
}
}
}
return 0;
}
int dinic(int x , int low)
{
if(x == t) return low;
int temp = low , i , k;
for(i = head[x] ; i ; i = next[i])
{
if(val[i] && dis[to[i]] == dis[x] + 1)
{
k = dinic(to[i] , min(temp , val[i]));
if(!k) dis[to[i]] = 0;
val[i] -= k , val[i ^ 1] += k;
if(!(temp -= k)) break;
}
}
return low - temp;
}
void dfs(int x)
{
int i;
for(i = 1 ; i <= n * m ; i ++ )
if(map[x][i] && flag[i])
flag[i] = 0 , dfs(i);
}
int main()
{
int i , j , k , x , y , ans = 0;
scanf("%d%d" , &n , &m);
s = 0 , t = n * m + 1;
for(i = 1 ; i <= n ; i ++ )
{
for(j = 1 ; j <= m ; j ++ )
{
scanf("%d%d" , &w[(i - 1) * m + j] , &k);
if(j > 1) map[(i - 1) * m + j][(i - 1) * m + j - 1] = 1;
while(k -- ) scanf("%d%d" , &x , &y) , map[(i - 1) * m + j][x * m + y + 1] = 1;
}
}
init();
for(i = 1 ; i <= n * m ; i ++ )
if(!flag[i])
dfs(i);
for(i = 1 ; i <= n * m ; i ++ )
{
if(flag[i])
{
if(w[i] >= 0) add(s , i , w[i]) , ans += w[i];
else add(i , t , -w[i]);
for(j = 1 ; j <= n * m ; j ++ )
if(map[j][i] && flag[j])
add(i , j , inf);
}
}
while(bfs()) ans -= dinic(s , inf);
printf("%d
" , ans);
return 0;
}