[BZOJ1565][NOI2009]植物大战僵尸-[网络流-最小割+最大点权闭合子图+拓扑排序]

Description

传送门

Solution

em本题知识点是用网络流求最大点权闭合子图。

闭合图定义：图中任何一个点u，若有边u->v，则v必定也在图中。

建图：运用最小割思想，将S向点权为正的点连边，流量为点权；点权为负的点向T连边，流量为点权的绝对值；原图之间的边流量为inf（表明不能割）。答案就是所有正点权之和-该网络流图的最小割（证明还未补qaq）

是不是觉得这个闭合图定义特别的眼熟？似乎可以套在这道题上。（题意：假如你要吃掉某个植物，需要先吃掉这个植物对应的集合，求最大的能源收入。）假如植物v保护u【ps：在u后面的植物也算作保护u】，则连边u->v。

当然需要注意，有些植物是RMB玩家哈哈（就是，它们的保护关系可以构成一个环），则这些植物和它们所保护的植物都是不能被吃掉的。RMB玩家可以用拓扑排序完美KO（当然，要把边反向建。原因。。因为我们还要找出所有环上植物们"所保护的植物"）

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

using namespace std;

const int inf=1e9;

int h[],tot=;

struct pas{int x,y,nxt,w,op,cost;}g[];

int dep[],S,T;

queue<int>q;

struct DINIC{

bool bfs()

{

    int x;

    memset(dep,,sizeof(dep));dep[S]=;

    while (!q.empty()) q.pop();

    q.push(S);

    while (!q.empty())

    {

        x=q.front();q.pop();

        for (int i=h[x];i;i=g[i].nxt)

        if (!dep[g[i].y]&&g[i].w)

        {

            dep[g[i].y]=dep[x]+;

            q.push(g[i].y);

            if (g[i].y==T) return ;

        }

    }

    return ;

}

int dfs(int x,int flow)

{

    if (x==T||(!flow))return flow;

    int temp=,js;

    for (int i=h[x];i;i=g[i].nxt)

    if (dep[g[i].y]==dep[x]+&&g[i].w)

    {

        js=dfs(g[i].y,min(flow,g[i].w));

        if (js)

        {

            g[i].w-=js;

            g[g[i].op].w+=js;

            temp+=js;

            flow-=js;

            if (!flow) return temp;

        }

    }

    if (!temp) dep[x]=;

    return temp;

}

    int dinic()

    {

        int ans=;

        while (bfs())

        ans+=dfs(S,inf);

        return ans;

    }

 }D;

void add(int x,int y,int w)

{

    g[++tot].x=x;g[tot].y=y;g[tot].w=w;g[tot].nxt=h[x];g[tot].op=tot+;h[x]=tot;

    g[++tot].x=y;g[tot].y=x;g[tot].w=;g[tot].nxt=h[y];g[tot].op=tot-;h[y]=tot;

}

int n,m,cnt,r,c,TOT,_v[];

int id(int x,int y) {return (x-)*m+y;}

bool not_cir[];int d[];

pas e[];

int e_tot=,e_h[];

void adde(int x,int y)

{

    e[++e_tot]=pas{x,y,e_h[x],,,};e_h[x]=e_tot;

    d[y]++;

}

void check()

{

    while (!q.empty()) q.pop();

    for (int i=;i<=n*m;i++) if (!d[i]) q.push(i),not_cir[i]=;

    while (!q.empty())

    {

        int x=q.front();q.pop();

        for (int i=e_h[x];i;i=e[i].nxt)

        {

            d[e[i].y]--;

            if (!d[e[i].y]) not_cir[e[i].y]=,q.push(e[i].y);

        }

    }

}

int main()

{

    scanf("%d%d",&n,&m);

    S=;T=n*m+;

    for (int i=;i<=n;i++) for (int j=;j<=m;j++)

    {

        scanf("%d",&_v[id(i,j)]);

        scanf("%d",&cnt);

        for (int k=;k<=cnt;k++)

        {

            scanf("%d%d",&r,&c);adde(id(i,j),id(r+,c+));

        }

        if (j!=m) adde(id(i,j+),id(i,j));

    }

    check();

    for (int i=;i<=e_tot;i++) if (not_cir[e[i].x]&&not_cir[e[i].y])add(e[i].y,e[i].x,inf);

    for (int i=;i<=n*m;i++) if (not_cir[i]) {if (_v[i]>) add(S,i,_v[i]),TOT+=_v[i];else add(i,T,-_v[i]);}

    int ans=;

    while (D.bfs())

        ans+=D.dfs(S,inf);

    printf("%d",TOT-ans);

}