【P2774】方格取数问题（贪心+最大流，洛谷）

首先，我们要读懂这道题，否则你会和我一开始产生一样的疑问，把所有的数都取走剩下一个最小的不就可以了么？？？然后我们发现样例完全不是这么回事。题目中所说的使相邻的两个数没有公共边，是指你去走的数，也就是取完之后矩阵里的空白格子。明白了这一点，我们可能会有一个比较基础的贪心思想，没错，就是隔一个取一个，但是这么做并不可行，具体反例很容易找。然后我们通过观察，发现这道题和某最大权闭合子图有些类似，如果我们全取所有点，删去最小割说不准可行。
开始考虑建图，首先所有的奇数格子连源点，偶数格子连汇点，边权为点权。他们之间的边只连奇数到偶数的，边权为inf，这么连是为了避免重复计算。然后直接DINIC最大流就可以了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<queue>

#define ll long long

#define inf 50000000

#define re register

#define id m*(i-1)+j

using namespace std;

struct po

{

    int from,to,dis,nxt;

}edge[];

int head[],cur[],dep[],n,m,s,t,u,num=-,x,y,l,tot,sum,d;

int nm,a[][];

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

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

inline int read()

{

    int x=,c=;

    char ch=' ';

    while((ch>''||ch<'')&&ch!='-')ch=getchar();

    while(ch=='-')c*=-,ch=getchar();

    while(ch<=''&&ch>='')x=x*+ch-'',ch=getchar();

    return x*c;

}

inline void add_edge(int from,int to,int dis)

{

    edge[++num].nxt=head[from];

    edge[num].from=from;

    edge[num].to=to;

    edge[num].dis=dis;

    head[from]=num;

}

inline void add(int from,int to,int dis)

{

    add_edge(from,to,dis);

    add_edge(to,from,);

}

inline bool bfs()

{

    memset(dep,,sizeof(dep));

    queue<int> q;

    while(!q.empty())

    q.pop();

    dep[s]=;

    q.push(s);

    while(!q.empty())

    {

        int now=q.front();

        q.pop();

        for(re int i=head[now];i!=-;i=edge[i].nxt)

        {

            int v=edge[i].to;

            if(dep[v]==&&edge[i].dis>)

            {

                dep[v]=dep[now]+;

                if(v==t)

                return ;

                q.push(v);

            }

        }

    }

    return ;

}

inline int dfs(int u,int dis)

{

    if(u==t)

    return dis;

    int diss=;

    for(re int i=head[u];i!=-;i=edge[i].nxt)

    {

        int v=edge[i].to;

        if(dep[v]==dep[u]+&&edge[i].dis!=)

        {

            int check=dfs(v,min(dis,edge[i].dis));

            if(check>)

            {

                diss+=check;

                dis-=check;

                edge[i].dis-=check;

                edge[i^].dis+=check;

                if(dis==) break;

            }

        }

    }

    return diss;

}

inline int dinic()

{

    int ans=;

    while(bfs())

    {

        for(re int i=;i<=t;i++)

        cur[i]=head[i];

        while(int d=dfs(s,inf))

        ans+=d;

    }

    return ans;

}

int main()

{

    memset(head,-,sizeof(head));

    n=read();m=read();

    s=;t=n*m+;

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

     for(re int j=;j<=m;j++)

     a[i][j]=read(),sum+=a[i][j];

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

     for(re int j=;j<=m;j++)

     {

         if((i+j)%==)

         add(s,id,a[i][j]);

         else

         add(id,t,a[i][j]);

         for(re int h=;h<=;h++)

         {

             int lx=i+dx[h],ly=j+dy[h];

             if(lx>=&&lx<=n&&ly>=&&ly<=m)

             if((lx+ly)%!=)

             add(id,(lx-)*m+ly,inf);

        }

     }

     cout<<sum-dinic();

}

巴特西

【P2774】方格取数问题（贪心+最大流，洛谷）

最新文章

热门文章