BZOJ 1565 [NOI2009]植物大战僵尸

题目大意

给你一个植物大战僵尸的模拟地图，给出各个植物之间的保护关系，请你求出一个序列使得僵尸从右面进场获得的权值最大。

题目特别长，数据范围特别小……网络流。

先构建一个最大权闭合子图的模型，被保护的植物指向保护的植物，之后去环跑一次Dinic就可以了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF=1<<30;
int n,m,S,T,score[2000010],w,inx,iny,ans,head[2000010],to[2000010],nex[2000010],val[2000010],tot=1,icnt[2000010],depth[2000010];
bool avai[2000010];
queue<int>q;
void addedge(int tx,int ty,int tz)
{
    to[++tot]=ty;
    nex[tot]=head[tx];
    head[tx]=tot;
    val[tot]=tz;
    to[++tot]=tx;
    nex[tot]=head[ty];
    head[ty]=tot;
    val[tot]=0;
    ++icnt[tx];
}
void topsort()
{
    while(!q.empty()) q.pop();
    for(int i=1;i<S;++i) if(!icnt[i]) avai[i]=true,q.push(i);
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        for(int i=head[tmp];i;i=nex[i])
            if(!val[i])
            {
                --icnt[to[i]];
                if(!icnt[to[i]]) avai[to[i]]=true,q.push(to[i]);
            }
    }
    return;
}
bool bfs()
{
    memset(depth,-1,sizeof depth);
    while(!q.empty()) q.pop();
    depth[S]=0;
    q.push(S);
    while(!q.empty())
    {
        int tmp=q.front();
        q.pop();
        for(int i=head[tmp];i;i=nex[i])
            if(avai[to[i]]&&val[i]&&depth[to[i]]==-1)
            {
                depth[to[i]]=depth[tmp]+1;
                if(to[i]==T) return true;
                q.push(to[i]);
            }
    }
    return false;
}
int dinic(int pos,int left)
{
    if(pos==T) return left;
    int nleft=left;
    for(int i=head[pos];i;i=nex[i])
        if(avai[to[i]]&&val[i]&&depth[to[i]]==depth[pos]+1)
        {
            int tmp=dinic(to[i],min(nleft,val[i]));
            if(!tmp) depth[to[i]]=-1;
            nleft-=tmp;
            val[i]-=tmp;
            val[i^1]+=tmp;
            if(!nleft) break;
        }
    return left-nleft;
}
void check()
{
    for(int i=1;i<S;++i) printf("%d ",avai[i]);
    printf("\n");
    for(int i=1;i<=T;++i) printf("%d ",icnt[i]);
    printf("\n");
}
int main()
{
    scanf("%d%d",&n,&m);
    S=n*m+1,T=n*m+2;
    avai[S]=avai[T]=true;
    for(int i=1;i<S;++i)
    {
        scanf("%d%d",&score[i],&w);
        if(i%m) addedge(i,i+1,INF);
        while(w--)
        {
            scanf("%d%d",&inx,&iny);
            addedge(inx*m+iny+1,i,INF);
        }
    }
    topsort();
    for(int i=1;i<S;++i)
    {
        if(!avai[i]) continue;
        if(score[i]>0) ans+=score[i],addedge(S,i,score[i]);
        if(score[i]<0) addedge(i,T,-score[i]);
    }
    while(bfs()) ans-=dinic(S,INF);
    printf("%d\n",ans);
    return 0;
}