BruceJay's Blog

BZOJ1565 植物大战僵尸

| Comments

To start with

这题Bruce看了题解。

Problem

Solution

如果u保护v,则连边u->v。
对于环,环上的点和环上的点保护的点都不可攻击,删去这些点再建图跑网络流。
如果v[x] 如果v[x]>0,则x向t连容量v[x]的边。
如果x保护y,则x向y连容量无限的边。
答案是所有正权的和-最大流。

Code

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 610;
const int M = 750100;
const int INF = 0x3f3f3f3f;
struct node{int v,nxt;}e[M];
struct Edge{int u,v,cap,flow,nxt;}edges[M];
int head[N]; int d[N]; bool vis[N];
int a[N]; int p[25][35]; int head2[N];
int h[N]; int cur[N];
queue<int> q;
int n,m,t,ans=0,cnt=0;

inline int read()
{
    int t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Addedge(int u,int v)
{
    e[++cnt].v=v; d[v]++;
    e[cnt].nxt=head[u]; head[u]=cnt;
}

void Addedge2(int u,int v,int cap)
{
    edges[++cnt]=(Edge){u,v,cap,0,head2[u]}; head2[u]=cnt;
    edges[++cnt]=(Edge){v,u,0,0,head2[v]}; head2[v]=cnt;
}

void Topo()
{
    for(int i=1;i<=n*m;i++) if(!d[i]) q.push(i);
    while(!q.empty()){
        int u=q.front(); q.pop(); vis[u]=true;
        for(int i=head[u];i;i=e[i].nxt){
            int v=e[i].v;
            if(--d[v]==0) q.push(v);
        }
    }
}

void Build()
{
    cnt=1; t=n*m+1;
    for(int u=1;u<=n*m;u++) if(vis[u]){
        if(a[u]>0) ans+=a[u],Addedge2(u,t,a[u]);
        else Addedge2(0,u,-a[u]);
        for(int i=head[u];i;i=e[i].nxt)
            if(vis[e[i].v]) Addedge2(u,e[i].v,INF);
    }
}

bool Bfs()
{
    memset(h,-1,sizeof(h));
    h[0]=0; q.push(0);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head2[u];i;i=edges[i].nxt)
            if(h[edges[i].v]==-1 && edges[i].cap>edges[i].flow){
                h[edges[i].v]=h[u]+1; q.push(edges[i].v);
            }
    }
    return h[t]!=-1;
}

int Dfs(int u,int now)
{
    int flow=0;
    if(u==t || !now) return now;
    for(int& i=cur[u];i;i=edges[i].nxt)
        if(h[edges[i].v]==h[u]+1){
            int f=Dfs(edges[i].v,min(now,edges[i].cap-edges[i].flow));
            edges[i].flow+=f; edges[i^1].flow-=f;
            flow+=f; now-=f; if(!now) break;
        }
    return flow;
}

void Dinic()
{
    while(Bfs()){
        memcpy(cur,head2,sizeof(cur));
        ans-=Dfs(0,INF);
    }
}

int main()
{
    int c,x,y;
    freopen("1565.in","r",stdin);
    freopen("1565.out","w",stdout);
    n=read(); m=read();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++) p[i][j]=++cnt;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        a[p[i][j]]=read();
        c=read();
        while(c--){
            x=read()+1; y=read()+1;
            Addedge(p[i][j],p[x][y]);
        }
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<m;j++)
        Addedge(p[i][j+1],p[i][j]);
    Topo();
    Build();
    Dinic();
    printf("%d",ans);
    return 0;
}

Last but not least

NOI的题想不出啊,前途茫然。。

Comments

comments powered by Disqus