关系复杂，数据小，网络流
依赖关系，最大权闭合子图
每个点还会无形地保护后面的植物
先tarjan找SCC，然后sz>1点不能攻击。再每个不能攻击的点dfs，其保卫的点也不能攻击
不能攻击的点选择上，就必须选择-inf的点。
最大权闭合子图跑即可
SCC的时候，每个点还要和后面的点连边。
代码：
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define reg register int #define il inline #define fi first #define se second #define mp make_pair #define numb (ch^'0') using namespace std; typedef long long ll; il void rd(int &x){ char ch;x=0;bool fl=false; while(!isdigit(ch=getchar()))(ch=='-')&&(fl=true); for(x=numb;isdigit(ch=getchar());x=x*10+numb); (fl==true)&&(x=-x); } namespace Miracle{ const int N=606; const int inf=0x3f3f3f3f; struct node{ int w; int nxt,to; }e[2*(N+N*N+N+2333)]; int hd[N],cnt; int n,m,s,t; vector<pair<int,int> >mem[N]; void add(int x,int y,int z,int typ){ e[++cnt].nxt=hd[x]; e[cnt].to=y; e[cnt].w=z; hd[x]=cnt; if(typ){ e[++cnt].nxt=hd[y]; e[cnt].to=x; e[cnt].w=0; hd[y]=cnt; } } int dfn[N]; int co[N]; int sz[N]; int tot,df; int low[N]; int sta[N],top; int in[N]; bool vis[N]; void tarjan(int x){ // cout<<" tarjan x "<<x<<endl; dfn[x]=low[x]=++df; in[x]=1; sta[++top]=x; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); } else if(in[y]) low[x]=min(low[x],dfn[y]); } if(low[x]==dfn[x]){ ++tot; int z; do{ z=sta[top]; co[z]=tot; ++sz[tot]; in[z]=0; --top; }while(z!=x); } } int d[N]; bool no[N]; int val[N]; int dfs(int x,int flow){ int res=flow; // cout<<" dfs "<<x<<" "<<flow<<endl; if(x==t) return flow; for(reg i=hd[x];i&&res;i=e[i].nxt){ int y=e[i].to; if(e[i].w&&d[y]==d[x]+1){ int k=dfs(y,min(res,e[i].w)); if(!k) d[y]=0; res-=k; e[i].w-=k; e[i^1].w+=k; } } return flow-res; } int q[N],l,r; bool bfs(){ memset(d,0,sizeof d); l=1,r=0; q[++r]=s; d[s]=1; while(l<=r){ int x=q[l++]; for(reg i=hd[x];i;i=e[i].nxt){ int y=e[i].to; if(e[i].w){ if(!d[y]){ d[y]=d[x]+1; q[++r]=y; if(y==t) return true; } } } } return false; }int num(int x,int y){ return (x-1)*m+y; } void dele(int x,int y){ // cout<<" dele x y "<<x<<" "<<y<<endl; if(vis[num(x,y)]) return; no[num(x,y)]=1; vis[num(x,y)]=1; if(y>1) dele(x,y-1); for(reg i=0;i<(int)mem[num(x,y)].size();++i){ if(!vis[num(mem[num(x,y)][i].fi,mem[num(x,y)][i].se)]){ dele(mem[num(x,y)][i].fi,mem[num(x,y)][i].se); } } } int main(){ rd(n);rd(m); int x,y; for(reg i=1;i<=n;++i){ for(reg j=1;j<=m;++j){ int id=num(i,j); rd(val[id]); int w; rd(w); for(reg k=1;k<=w;++k){ rd(x);rd(y); ++x;++y; add(id,num(x,y),0,0); mem[id].push_back(mp(x,y)); } if(j!=1){ add(id,num(i,j-1),0,0); } } } for(reg i=1;i<=n*m;++i){ if(!dfn[i]){ tarjan(i); } } for(reg i=1;i<=n*m;++i){ if(sz[co[i]]>1){ no[i]=1; } } for(reg i=1;i<=n;++i){ for(reg j=1;j<=m;++j){ if(!vis[num(i,j)]&&no[num(i,j)]){ dele(i,j); } } } s=0; t=n*m+2; val[n*m+1]=-inf; memset(hd,0,sizeof hd); cnt=1; int ans=0; // for(reg i=1;i<=n;++i){ // for(reg j=1;j<=m;++j){ // cout<<no[num(i,j)]<<" "; // }cout<<endl; // } // for(reg i=1;i<=n;++i){ for(reg j=1;j<=m;++j){ if(j!=m) { add(num(i,j),num(i,j+1),inf,1); } for(reg k=0;k<(int)mem[num(i,j)].size();++k){ add(num(mem[num(i,j)][k].fi,mem[num(i,j)][k].se),num(i,j),inf,1); } if(no[num(i,j)]){ add(num(i,j),n*m+1,inf,1); } if(val[num(i,j)]>0){ ans+=val[num(i,j)]; add(s,num(i,j),val[num(i,j)],1); }else{ add(num(i,j),t,-val[num(i,j)],1); } } } add(n*m+1,t,inf,1); // cout<<" after no 3 "<<endl; int flow=0; while(bfs()){ while(flow=dfs(s,inf)) ans-=flow; } cout<<ans; return 0; } } signed main(){ Miracle::main(); return 0; } /* Author: *Miracle* Date: 2019/1/16 16:45:42 */