题意：
给定一张$n imes m$的网格图，每个点有个植物，价值$Score$，能控制点集$S$。
现在有一些僵尸攻击这些植物，每个僵尸可以任选一行，然后从第$m+1$列一直往左走，消灭遇到的所有植物。
如果一个僵尸走到某个格子，它被一个没被消灭的植物控制着，则这个僵尸会被消灭。
你可以派出任意个僵尸，求攻击植物所能获得的最大价值。
$n,mleq 30,-10^4 leq Scoreleq 10^4$。
题解：
互相有控制关系的网络流问题基本就是最大权闭合子图，于是直接无脑建模就做完了。
注意到如果两个点位于同一个强联通分量，那么它们永远没法产生贡献。
朴素的做法是用$tarjan$判掉，但其实也可以拓扑排序，最后没在队列里的点直接删掉即可。
复杂度$O(能过)$。
套路：
- 互相有控制关系的网络流问题$ ightarrow$最大权闭合子图。
- 判强联通分量$ ightarrow$Tarjan或拓扑排序。
代码：
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<queue> #include<stack> #define maxn 1000005 #define maxm 500005 #define inf 0x7fffffff #define ll long long using namespace std; int N,M,A[maxn],hd[maxn],to[maxn<<1]; int T,S,cnt=1,nxt[maxn<<1],fl[maxn<<1]; int dfn[maxn],low[maxn],dis[maxn],num; bool ins[maxn],vis[maxn]; stack<int> s; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline int calc(int x,int y){return x*M+y+1;} inline void addedge(int u,int v,int w){ to[++cnt]=v,fl[cnt]=w,nxt[cnt]=hd[u],hd[u]=cnt; to[++cnt]=u,fl[cnt]=0,nxt[cnt]=hd[v],hd[v]=cnt; } inline bool spfa(){ memset(dis,-1,sizeof(dis)); queue<int> q; q.push(S),dis[S]=0; while(!q.empty()){ int u=q.front(); q.pop(); if(u==T) break; for(int i=hd[u];i;i=nxt[i]){ int v=to[i]; if(dis[v]==-1 && fl[i]>0) dis[v]=dis[u]+1,q.push(v); } } return dis[T]!=-1; } inline int dfs(int u,int flow){ if(u==T) return flow; int sum=0; for(int i=hd[u];i;i=nxt[i]){ int v=to[i]; if(dis[v]==dis[u]+1 && fl[i]>0){ int f=dfs(v,min(flow,fl[i])); fl[i]-=f,fl[i^1]+=f,sum+=f,flow-=f; if(!flow) break; } } if(sum==0) dis[u]=-1; return sum; } inline int Dinic(){ int ans=0; while(spfa()) ans+=dfs(S,inf); return ans; } inline void tarjan(int u){ dfn[u]=low[u]=++num,ins[u]=1,s.push(u); for(int i=hd[u];i;i=nxt[i]){ int v=to[i]; if(fl[i]!=inf) continue; if(!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]); else if(ins[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]){ if(s.top()==u) s.pop(),ins[u]=0; else{ while(s.top()!=u) vis[s.top()]=1,ins[s.top()]=0,s.pop(); vis[s.top()]=1,ins[s.top()]=0,s.pop(); } } return; } int main(){ N=read(),M=read(); for(int i=0;i<N;i++){ for(int j=0;j<M;j++){ int tp=calc(i,j); A[tp]=read(); int nm=read(); for(int k=1;k<=nm;k++){ int x=read(),y=read(); addedge(calc(x,y),tp,inf); } } for(int j=0;j<M-1;j++) addedge(calc(i,j),calc(i,j+1),inf); } for(int i=1;i<=N*M;i++) if(!dfn[i]) tarjan(i); S=0,T=N*M+1; int sum=0; for(int i=0;i<N;i++) for(int j=0;j<M;j++){ int tp=calc(i,j); if(vis[tp]) continue; if(A[tp]<0) addedge(tp,T,-A[tp]); else sum+=A[tp],addedge(S,tp,A[tp]); } printf("%d ",sum-Dinic()); return 0; }