04/11
00:10
OI

[NOI2009]植物大战僵尸

[NOI2009]植物大战僵尸

最大权闭合子图入门题。

把题目中的植物向左边的植物和可以攻击到的植物连边,构成了一张图。显然环是无敌的,去掉即可。我们需要在剩下的环上找出可以取到的最大值。

闭合子图,是有向图一个子图,其中所有点出边指向的点还在子图内。这道题中如果要攻击一个植物,要把连向它的植物都打掉,即一个闭合子图。本题要求出最大权闭合子图。

从S向所有val>=0的点连val,所有val<0的点向T连-val,图中原有的边连INF。最大权=正val和-最小割=正val和-最大流。

这里只感性的理解一下:显然INF都不会被割掉,最小割中割掉的边都是和S或T连着的。割掉和S的连接表示不选,割掉和T的连接表示选的代价。割的最少时选中的最大,然后我们都知道最小割=最大流。最大权闭合子图的具体证明可以看国集论文。

所以这题只需要先建个图出来,拓扑排序去掉环,然后跑个最大流就行了。

代码写的特别丑仅供参考…(

#include <bits/stdc++.h>
using namespace std;

namespace kai586123{
inline int rd(){
    int a=1,b=0; char c=getchar();
    while(!isdigit(c)) a=c=='-'?0:1,c=getchar();
    while(isdigit(c)) b=b*10+c-'0',c=getchar();
    return a?b:-b;
}

const int S=50,N=233333,INF=0x3f3f3f3f;

struct Graph{
    int to,nxt,flow;
}g[N*2];

int head[N],tot=1,n,m,id[S][S],num,s=++num,t=++num,
    val[N],in[N],sum,que[N*10],l,r,dis[N];
bool vis[N];

vector<int> gg[N];

void addedge(int x,int y,int f){
    g[++tot].to=y,g[tot].nxt=head[x],
    g[tot].flow=f,head[x]=tot;
}

void add(int x,int y,int f){
    addedge(x,y,f);
    addedge(y,x,0);
}

bool bfs(){
    memset(dis,0,sizeof(dis));
    dis[que[l=0,r=1]=s]=1;
    while(l!=r){
        int x=que[++l];
        for(int i=head[x];i;i=g[i].nxt){
            if(g[i].flow&&!dis[g[i].to]){
                dis[g[i].to]=dis[x]+1;
                que[++r]=g[i].to;
            }
        }
    }
    return dis[t];
}

int dfs(int x,int mf){
    if(x==t) return mf;
    int used=0,tmp;
    for(int i=head[x];i;i=g[i].nxt){
        if(g[i].flow&&dis[g[i].to]==dis[x]+1){
            tmp=dfs(g[i].to,min(g[i].flow,mf-used));
            used+=tmp,g[i].flow-=tmp,g[i^1].flow+=tmp;
            if(!tmp) dis[g[i].to]=-1;
            if(used==mf) break;
        }
    }
    if(!used) dis[x]=-1;
    return used;
}

void read(){
    n=rd(),m=rd();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            id[i][j]=++num;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            val[id[i][j]]=rd();
            int cnt=rd();
            while(cnt--){
                int x=rd()+1,y=rd()+1;
                ++in[id[x][y]];
                gg[id[i][j]].push_back(id[x][y]);
            }
            if(j!=m){
                ++in[id[i][j]];
                gg[id[i][j+1]].push_back(id[i][j]);
            }
        }
    }
}

void toposort(){
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j)
            if(!in[id[i][j]]){
                vis[id[i][j]]=true;
                que[++r]=id[i][j];
            }
    while(l!=r){
        int x=que[++l];
        for(unsigned i=0;i<gg[x].size();++i){
            int y=gg[x][i];
            if(!--in[y]&&!vis[y]){
                vis[y]=true;
                que[++r]=y;
            }
        }
    }
}

void build(){
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            int x=id[i][j];
            if(vis[x]){
                if(val[x]>=0){
                    sum+=val[x];
                    add(s,x,val[x]);
                }
                else add(x,t,-val[x]);
                for(unsigned k=0;k<gg[x].size();++k){
                    int y=gg[x][k];
                    if(vis[y])
                        add(y,x,INF);
                }
            }
        }
    }
}

void solve(){
    while(bfs()) sum-=dfs(s,INF);
    cout<<sum<<endl;
}

void love(){
    read();
    toposort();
    build();
    solve();
}
}

signed main(){
#ifndef ONLINE_JUDGE
    freopen("data.txt","r",stdin);
#endif
    return kai586123::love(),0;
}