https://www.luogu.org/problemnew/show/P2805
最大权闭合子图的特点是，假如你要选一个结点，则要先选中它的所有子节点。正权连S负权连T，容量为绝对值，原图有向边连容量INF。
这里的特点是在于假如这些结点形成了回路，那么不能选中其中任何一个因为没有突破口。
至于为什么要反向建图，是为了使用拓扑排序把回路以及进入回路的结点剪掉，但是不影响网络流图中从属于回路的子节点。
（反向建图后，原本从属于回路的变成可以进入回路，拓扑排序则会把入度非0的剪掉则一举剪除所有不可取的结点）
#include<bits/stdc++.h>
using namespace std;
#define ll long long /* dinic begin */ const int MAXN=;
const int MAXM=;
//注意网络流要预留反向边
const int INF=0x3f3f3f3f;
struct Edge{
int to,next,cap,flow;
}edge[MAXM]; int tol;
int head[MAXN]; void init(){
tol=;
memset(head,-,sizeof(head));
} void addedge(int u,int v,int w,int rw=){
edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=;
edge[tol].next=head[u];head[u]=tol++;
edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=;
edge[tol].next=head[v];head[v]=tol++;
} vector<Edge> tmpEdge[];
vector<int> G[]; void addedge2(int u,int v,int w,int rw=){
Edge e;
e.to=v;
e.cap=w;
e.flow=;
tmpEdge[u].push_back(e);
} void copyedge(Edge e,int u){
int v=e.to;
int w=e.cap;
addedge(u,v,w);
} int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
bool bfs(int s,int t,int n){
int front=,tail=;
memset(dep,-,sizeof(dep[])*(n+));
dep[s]=;
Q[tail++]=s;
while(front<tail){
int u=Q[front++];
for(int i=head[u];i!=-;i=edge[i].next){
int v=edge[i].to;
if(edge[i].cap>edge[i].flow&&dep[v]==-){
dep[v]=dep[u]+;
if(v==t)
return true;
Q[tail++]=v;
}
}
}
return false;
} int dinic(int s,int t,int n=-){
int maxflow=;
if(n==-)
n=t;
n++;//假如把t作为编号最后的点的话传入t就可以了
while(bfs(s,t,n)){
for(int i=;i<n;i++)cur[i]=head[i];
int u=s,tail=;
while(cur[s]!=-){
if(u==t){
int tp=INF;
for(int i=tail-;i>=;i--){
tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow); }
maxflow+=tp;
for(int i=tail-;i>=;i--){
edge[sta[i]].flow+=tp;
edge[sta[i]^].flow-=tp;
if(edge[sta[i]].cap-edge[sta[i]].flow==)
tail=i;
}
u=edge[sta[tail]^].to; }
else if(cur[u]!=-&&edge[cur[u]].cap>edge[cur[u]].flow
&&dep[u]+==dep[edge[cur[u]].to]){
sta[tail++]=cur[u];
u=edge[cur[u]].to;
}
else{
while(u!=s&&cur[u]==-){
u=edge[sta[--tail]^].to;
}
cur[u]=edge[cur[u]].next;
}
}
}
return maxflow;
} /* dinic end */ int n,m;
inline int id(int i,int j){
return (i-)*m+j;
} int indeg[];
bool vis[]; void toposort(){
queue<int>q;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
int u=id(i,j);
if(indeg[u]==){
vis[u]=true;
q.push(u);
}
}
} while(!q.empty()){
int u=q.front();
q.pop();
for(auto v:G[u]){
indeg[v]--;
if(vis[v]==false&&indeg[v]==){
vis[v]=true;
q.push(v);
}
}
} //vis[i]==true的点是在拓扑排序中出现过的点
//若有其他需要可以改成int vist?
} int sc[]; int main(){
init();
scanf("%d%d",&n,&m);
int s=,t=n*m+; for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
int w;
int u=id(i,j);
scanf("%d%d",&sc[u],&w);
while(w--){
int ii,jj;
scanf("%d%d",&ii,&jj);
ii++,jj++;
int v=id(ii,jj);
addedge2(v,u,INF);
indeg[v]++;
G[u].push_back(v);
}
if(j+<=m){
int v=id(i,j+);
addedge2(u,v,INF);
indeg[u]++;
G[v].push_back(u);
//要反向建图，这样进入环的链其实是可以在网络流建最大权闭合子图的
//最大权闭合子图的关系是一个点的从属结点都要选上自己才能选中
//反向建图后，链上的点就是闭合子图的从属节点，可以只选中链上的点而不选择他们要进入的环
}
}
} toposort();
ll sum=;
int cnt=;
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
int u=id(i,j);
if(vis[u]==false)
continue; if(sc[u]>=){
sum+=sc[u];
addedge(s,u,sc[u]);
cnt++;
}
else{
addedge(u,t,-sc[u]);
}
for(auto k:tmpEdge[u]){
if(vis[k.to])
copyedge(k,u);
}
}
} //printf("cnt=%d sum=%lld\n",cnt,sum);
printf("%lld\n",sum-(ll)dinic(s,t));
}