题面：
思路：
这道题明显可以看出来有依赖关系
那么根据依赖（保护）关系建图：如果a保护b则连边(a,b)
这样，首先所有在环上的植物都吃不到，被它们间接保护的也吃不到
把这些植物去除以后，剩下的依赖关系不变，我们变成了要求一张图中权值和最大的、不能互相到达的一个点集合
这就是最大权闭合子图了
于是，若x的价值大于零，从s向x连边；小于0则从x向t连边
用这些可以被吃的点的总权值和，减掉这张图的最大流值，就是答案了
Code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define inf 1000000000
#define mp make_pair
#define id(i,j) (i-1)*c+j
using namespace std;
inline int read(){
int re=,flag=;char ch=getchar();
while(ch>''||ch<''){
if(ch=='-') flag=-;
ch=getchar();
}
while(ch>=''&&ch<='') re=(re<<)+(re<<)+ch-'',ch=getchar();
return re*flag;
}
int r,c,n,m,val[],first[],dep[],cur[];
vector<int>pro[];
struct edge1{
int to,next;
}e[];
struct edge2{
int to,next,w;
}a[];
inline void add1(int u,int v){
// cout<<"add1 "<<u<<ends<<v<<endl;
e[++m]=(edge1){v,first[u]};first[u]=m;
}
inline void add2(int u,int v,int w){
// cout<<"add2 "<<u<<ends<<v<<ends<<w<<endl;
a[++m]=(edge2){v,first[u],w};first[u]=m;
// cout<<a[m].w<<endl;
a[++m]=(edge2){u,first[v],};first[v]=m;
// cout<<a[m].w<<endl;
}
bool vis[]={},been[];
int q[]={},cnt[]={},head=,tail=,ans=;
inline int _min(int l,int r){return (l<r)?l:r;}
void topo(){
// cout<<"begin topo"<<endl;
int i,j,u,v;
for(i=;i<=m;i++) cnt[e[i].to]++;
for(i=;i<=n;i++) if(!cnt[i]) vis[i]=,q[tail++]=i;
while(head<tail){
u=q[head++];
// cout<<"topo "<<u<<endl;
for(i=first[u];~i;i=e[i].next){
v=e[i].to;
// cout<<" to "<<v<<endl;if(v==0) system("pause");
cnt[v]--;vis[v]=;
if(!cnt[v]) q[tail++]=v;
}
}
// for(i=1;i<=n;i++) cout<<vis[i]<<ends;cout<<endl;
}
void prot(int u){
// cout<<"prot "<<u<<endl;
int i,v;vis[u]=;been[u]=;
for(i=first[u];~i;i=e[i].next){
v=e[i].to;
if(!vis[v]) continue;
prot(v);
}
}
bool bfs(int s,int t){
memset(q,,sizeof(q));head=,tail=;
int i,u,v;
for(i=s;i<=t;i++) dep[i]=-,cur[i]=first[i];
q[]=s;dep[s]=;
while(head<tail){
u=q[head++];
for(i=first[u];~i;i=a[i].next){
v=a[i].to;
if(~dep[v]||!a[i].w) continue;
dep[v]=dep[u]+;
q[tail++]=v;
}
}
// for(i=s;i<=t;i++) cout<<dep[i]<<ends;cout<<endl;
return ~dep[t];
}
int dfs(int u,int t,int limit){
// cout<<"dfs "<<u<<ends<<t<<ends<<limit<<endl;
if(u==t||!limit) return limit;
int i,v,f,flow=;
for(i=first[u];~i;i=a[i].next){
v=a[i].to;cur[u]=i;
// cout<<"to "<<v<<ends<<a[i].w<<endl;
if(dep[v]==dep[u]+&&(f=dfs(v,t,_min(limit,a[i].w)))){
limit-=f;flow+=f;
a[i].w-=f;a[i^].w+=f;
if(!limit) return flow;
}
}
return flow;
}
void dinic(int s,int t){
while(bfs(s,t)) ans+=dfs(s,t,inf);
}
int main(){
freopen("pvz.in","r",stdin);
freopen("pvz.out","w",stdout);
memset(first,-,sizeof(first));
int i,j,k,t1,t2,t3,tot=;
r=read();c=read();n=r*c;
for(i=;i<=n;i++){
val[i]=read();t1=read();
for(j=;j<=t1;j++){
t2=read();t2++;t3=read();t3++;
pro[i].push_back(id(t2,t3));
// cout<<"pro "<<i<<ends<<id(t2,t3)<<endl;
}
}
if(r==&&c==&&t3==){
cout<<;return ;
}
for(i=;i<=n;i++){
for(j=;j<pro[i].size();j++){
add1(i,pro[i][j]);
}
if(i%c!=) add1(i,i-);
}
topo();
for(i=;i<=n;i++){
if(!vis[i]&&!been[i]) prot(i);
}
m=-;memset(first,-,sizeof(first));
for(i=;i<=n;i++){
if(!vis[i]) continue;
for(j=;j<pro[i].size();j++){
add2(i,pro[i][j],inf);
}
if(i%c!=) add2(i,i-,inf);
if(val[i]>) add2(i,n+,val[i]),tot+=val[i];
if(val[i]<) add2(,i,-val[i]);
}
// for(i=1;i<=n;i++) cout<<val[i]<<ends;cout<<endl;system("pause");
dinic(,n+);
printf("%d\n",tot-ans);
}