洛谷P2774 方格取数问题

题意：

给定一个网格图，每个格子有点权，要求取出的格子没有公共边，问权值和的最大值。

知识点：

最小割

解法：

相邻两个点的横纵坐标之和必定异奇偶，所以只要同奇偶的点必定可以同时取，而且异奇偶的也不一定不能同时取（只有相邻不能）。所以这是一个二分图。S向奇数那边连边，连点权，偶数向T连点权。中间假如是相邻的点，奇数向偶数连INF的边，因为是最小割，所以一定割不掉中间的INF边。此时割掉一条边表示的就是不选这个点，因为最小割后图不连通，所以肯定不存在一条从S到奇数再到偶数最后到T的路径，所以必定满足没有公共边，所以最大流=最小割即可求出最小不选的权值。用总数减去即可。

备注：

遇到这种网格图的题假如有什么限制的，优先想想最小割，用INF边来表示冲突，用总量-不选的权值=选的权值来计算。

代码：

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

const int maxn=10010,maxm=maxn*10,inf=0x7fffffff;
int n,m,tot,S,T,head[maxn],dis[maxn],id[110][110],cnt,cur[maxn];
struct node
{
    int nxt,to,w;
}edge[maxm];
queue<int>q;

int read()
{
    int x=0;
    char c=getchar();
    while (c<48||c>57)
        c=getchar();
    while (c>=48&&c<=57)
        x=(x<<1)+(x<<3)+(c^48),c=getchar();
    return x;
}

void add(int u,int v,int w)
{
    edge[++tot]=(node){head[u],v,w};
    head[u]=tot;
}

void link(int u,int v,int w)
{
    add(u,v,w);
    add(v,u,0);
}

bool bfs()
{
    memset(dis,0,sizeof(dis));
    while (!q.empty())
        q.pop();
    int i,u,v;
    q.push(S);
    dis[S]=1;
    while (!q.empty())
    {
        u=q.front();
        q.pop();
        for (i=head[u];i;i=edge[i].nxt)
        {
            v=edge[i].to;
            if (!dis[v]&&edge[i].w>0)
            {
                dis[v]=dis[u]+1;
                q.push(v);
            }
        }
    }
    return dis[T];
}

int dfs(int u,int flow)
{
    if (u==T)
        return flow;
    int v,res=flow,tmp;
    for (int &i=cur[u];i;i=edge[i].nxt)
    {
        v=edge[i].to;
        if (dis[v]==dis[u]+1&&edge[i].w>0)
        {
            tmp=dfs(v,min(res,edge[i].w));
            res-=tmp;
            edge[i].w-=tmp;
            edge[i^1].w+=tmp;
            if (!res)
                break;
        }
    }
    return flow-res;
}

int dinic()
{
    int ans=0,i,tmp;
    while (bfs())
    {
        for (i=1;i<=T;i++)
            cur[i]=head[i];
        tmp=dfs(S,inf);
        if (!tmp)
            break;
        ans+=tmp;
    }
    return ans;
}

int main()
{
    int i,j,val;
    int ans=0;
    n=read(),m=read();
    tot=1;
    S=n*m+1,T=S+1;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            id[i][j]=(++cnt);
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
        {
            val=read();
            ans+=val;
            if ((i+j)&1)
            {
                link(S,id[i][j],val);
                if (i>=2)
                    link(id[i][j],id[i-1][j],inf);
                if (i<=n-1)
                    link(id[i][j],id[i+1][j],inf);
                if (j>=2)
                    link(id[i][j],id[i][j-1],inf);
                if (j<=m-1)
                    link(id[i][j],id[i][j+1],inf);
            }
            else
            {
                link(id[i][j],T,val);
                if (i>=2)
                    link(id[i-1][j],id[i][j],inf);
                if (i<=n-1)
                    link(id[i+1][j],id[i][j],inf);
                if (j>=2)
                    link(id[i][j-1],id[i][j],inf);
                if (j<=m-1)
                    link(id[i][j+1],id[i][j],inf);
            }
        }
    printf("%d\n",ans-dinic());
    return 0;
}

洛谷P2774 方格取数问题

原文：https://www.cnblogs.com/Ronald-MOK1426/p/12305327.html