bzoj3774 最优选择

题目描述：

小N手上有一个N*M的方格图，控制某一个点要付出Aij的代价，然后某个点如果被控制了，或者他周围的所有点(上下左右)都被控制了，那么他就算是被选择了的。一个点如果被选择了，那么可以得到Bij的回报，现在请你帮小N选一个最优的方案，使得回报-代价尽可能大。

题解：

最开始以为是最大权闭合子图裸题，后来发现少了点什么……

一般的图是正权->负权，但是这道题是负权->正权。

于是考虑拆点+最小割。

先假设手里拿着有所有的价值，即$\sum(b)$

对于一个点有三种情况：

1.占领这个点，此时代价为$a$；

2.不占领这个点，但是上下左右的某一个格子被占领了，此时代价为$0$；

2.不占领这个点，而且上下左右都是空的，此时代价为$b$；

我们可以先将棋盘黑白染色，然后建图。

重点是怎么建图。

拆点，每个点拆出的$x,y$之间连一条容量为$b$的边，源点向黑点的$x$连容量为$a$的边，白点的$y$向汇点连一条容量为$a$的边。

黑$x$向附近的白$x$连容量为$inf$的边，$y$同理。

意思是强迫割掉$a$，$b$或相邻点的$a$。

代码：

#include<queue>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N = ;

const int inf = 0x3f3f3f3f;

template<typename T>

inline void read(T&x)

{

    T f = ,c = ;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){c=c*+ch-'';ch=getchar();}

    x = f*c;

}

int n,m,hed[N],cnt=-,S=,T,cur[N];

int dx[]={-,,,};

int dy[]={,,-,};

bool check(int x,int y){return x>=&&y>=&&x<=n&&y<=m;}

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

ll ans;

struct EG

{

    int to,nxt;

    ll w;

}e[*N];

void ae(int f,int t,ll w)

{

    e[++cnt].to = t;

    e[cnt].nxt  = hed[f];

    e[cnt].w    = w;

    hed[f] = cnt;

}

void AE(int f,int t,ll w)

{

    ae(f,t,w);

    ae(t,f,);

}

int dep[N];

bool vis[N];

bool bfs()

{

    memset(dep,0x3f,sizeof(dep));

    memcpy(cur,hed,sizeof(cur));

    queue<int>q;

    dep[]=,vis[]=;q.push();

    while(!q.empty())

    {

        int u = q.front();

        q.pop();

        for(int j=hed[u];~j;j=e[j].nxt)

        {

            int to = e[j].to;

            if(e[j].w&&dep[to]>dep[u]+)

            {

                dep[to]=dep[u]+;

                if(!vis[to])vis[to]=,q.push(to);

            }

        }

        vis[u]=;

    }

    return dep[T]!=inf;

}

ll dfs(int u,ll lim)

{

    if(u==T||!lim)return lim;

    ll fl=,f;

    for(int j=cur[u];~j;j=e[j].nxt)

    {

        cur[u]=j;

        int to = e[j].to;

        if(dep[to]==dep[u]+&&(f=dfs(to,min(lim,e[j].w))))

        {

            fl+=f,lim-=f;

            e[j].w-=f,e[j^].w+=f;

            if(!lim)break;

        }

    }

    return fl;

}

ll dinic()

{

    ll ret=;

    while(bfs())

        ret+=dfs(S,inf);

    return ret;

}

int main()

{

    read(n),read(m);

    if(n==&&m==)

    {

        int a,b;

        read(a),read(b);

        if(b>a)ans=b-a;

        printf("%lld\n",ans);

        return ;

    }

    memset(hed,-,sizeof(hed));

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

        for(int a,j=;j<=m;j++)

        {

            read(a);

            if((i+j)&)AE(S,_id(i,j)<<,a);

            else AE(_id(i,j)<<|,T,a);

        }

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

        for(int b,j=;j<=m;j++)

        {

            read(b);ans+=b;

            int u = _id(i,j);

            AE(u<<,u<<|,b);

            if((i+j)&)

            {

                for(int x,y,o=;o<;o++)

                {

                    x = dx[o]+i,y = dy[o]+j;

                    if(check(x,y))

                    {

                        int t = _id(x,y);

                        AE(u<<,t<<,inf);

                        AE(u<<|,t<<|,inf);

                    }

                }

            }

        }

    printf("%lld\n",ans-dinic());

    return ;

}

巴特西

bzoj3774 最优选择

最新文章

热门文章