洛谷

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=20100;
const int MAXM=20000100;
//注意网络流要预留反向边
const int INF=0x3f3f3f3f;
struct Edge{
    int to,next,cap,flow;
}edge[MAXM];

int tol;
int head[MAXN];

void init(){
    tol=2;
    memset(head,-1,sizeof(head));
}

void addedge(int u,int v,int w,int rw=0){
    edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;
    edge[tol].next=head[u];head[u]=tol++;
    edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0;
    edge[tol].next=head[v];head[v]=tol++;
}

vector<Edge> tmpEdge[800];
vector<int> G[800];

void addedge2(int u,int v,int w,int rw=0){
    Edge e;
    e.to=v;
    e.cap=w;
    e.flow=0;
    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=0,tail=0;
    memset(dep,-1,sizeof(dep[0])*(n+1));
    dep[s]=0;
    Q[tail++]=s;
    while(front<tail){
        int u=Q[front++];
        for(int i=head[u];i!=-1;i=edge[i].next){
            int v=edge[i].to;
            if(edge[i].cap>edge[i].flow&&dep[v]==-1){
                dep[v]=dep[u]+1;
                if(v==t)
                    return true;
                Q[tail++]=v;
            }
        }
    }
    return false;
}

int dinic(int s,int t,int n=-1){
    int maxflow=0;
    if(n==-1)
        n=t;
    n++;//假如把t作为编号最后的点的话传入t就可以了
    while(bfs(s,t,n)){
        for(int i=0;i<n;i++)cur[i]=head[i];
        int u=s,tail=0;
        while(cur[s]!=-1){
            if(u==t){
                int tp=INF;
                for(int i=tail-1;i>=0;i--){
                    tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);

                }
                maxflow+=tp;
                for(int i=tail-1;i>=0;i--){
                    edge[sta[i]].flow+=tp;
                    edge[sta[i]^1].flow-=tp;
                    if(edge[sta[i]].cap-edge[sta[i]].flow==0)
                        tail=i;
                }
                u=edge[sta[tail]^1].to;

            }
            else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow
                    &&dep[u]+1==dep[edge[cur[u]].to]){
                sta[tail++]=cur[u];
                u=edge[cur[u]].to;
            }
            else{
                while(u!=s&&cur[u]==-1){
                    u=edge[sta[--tail]^1].to;
                }
                cur[u]=edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}

/* dinic end */

int n,m;
inline int id(int i,int j){
    return (i-1)*m+j;
}

int indeg[800];
bool vis[800];

void toposort(){
    queue<int>q;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int u=id(i,j);
            if(indeg[u]==0){
                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]==0){
                vis[v]=true;
                q.push(v);
            }
        }
    }

    //vis[i]==true的点是在拓扑排序中出现过的点
    //若有其他需要可以改成int vist?
}

int sc[800];

int main(){
    init();
    scanf("%d%d",&n,&m);
    int s=0,t=n*m+1;


    for(int i=1;i<=n;i++){
        for(int j=1;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+1<=m){
                int v=id(i,j+1);
                addedge2(u,v,INF);
                indeg[u]++;
                G[v].push_back(u);
                //要反向建图，这样进入环的链其实是可以在网络流建最大权闭合子图的
                //最大权闭合子图的关系是一个点的从属结点都要选上自己才能选中
                //反向建图后，链上的点就是闭合子图的从属节点，可以只选中链上的点而不选择他们要进入的环
            }
        }
    }

    toposort();
    ll sum=0;
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            int u=id(i,j);
            if(vis[u]==false)
                continue;

            if(sc[u]>=0){
                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
",cnt,sum);
    printf("%lld
",sum-(ll)dinic(s,t));
}