首页 > 代码库 > 洛谷 P2774 方格取数问题

洛谷 P2774 方格取数问题

题目背景

none!

题目描述

在一个有 m*n 个方格的棋盘中,每个方格中有一个正整数。现要从方格中取数,使任意 2 个数所在方格没有公共边,且取出的数的总和最大。试设计一个满足要求的取数算法。对于给定的方格棋盘,按照取数要求编程找出总和最大的数。

输入输出格式

输入格式:

 

第 1 行有 2 个正整数 m 和 n,分别表示棋盘的行数和列数。接下来的 m 行,每行有 n 个正整数,表示棋盘方格中的数。

 

输出格式:

 

程序运行结束时,将取数的最大总和输出

 

输入输出样例

输入样例#1:
3 31 2 33 2 32 3 1 
输出样例#1:
11

说明

none!

解题思路

  一道和骑士共存问题差不多的题目,二分图黑白染色后跑最大独立集,这里每个白格向四周连边,而不是马能攻击到的地方(废话)。

源代码

#include<queue>#include<cstdio>#include<cstring>#include<algorithm>int n,m;int a[1000][1000]={0};int S=0;inline int id(int x,int y){    return (x-1)*m+y;}int s,t;struct Edge{    int next,to,flow;}e[1000010];int cnt=2,head[1000]={0};void add(int u,int v,int f){    e[cnt]={head[u],v,f};    head[u]=cnt++;    e[cnt]={head[v],u,0};    head[v]=cnt++;}int dis[1000]={0};bool bfs(){    memset(dis,0,sizeof(dis));    std::queue<int> q;    q.push(s);    dis[s]=1;    while(!q.empty())    {        int u=q.front();q.pop();        for(int i=head[u];i;i=e[i].next)        {            int v=e[i].to;            if(dis[v]||!e[i].flow) continue;            dis[v]=dis[u]+1;            q.push(v);        }    }    return dis[t]!=0;}int dfs(int u,int f){    if(u==t||f==0) return f;    int flow_sum=0;    for(int i=head[u];i;i=e[i].next)    {        int v=e[i].to;        if(dis[v]!=dis[u]+1||!e[i].flow) continue;        int temp=dfs(v,std::min(e[i].flow,f-flow_sum));        e[i].flow-=temp;        e[i^1].flow+=temp;        flow_sum+=temp;        if(flow_sum>=f) break;    }    if(!flow_sum) dis[u]=-1;    return flow_sum;}int dinic(){    int ans=0;    while(bfs())    {        while(int temp=dfs(s,0x7fffffff))            ans+=temp;    }    return ans;}int main(){    scanf("%d%d",&n,&m);    s=n*m+1,t=s+1;    for(int i=1;i<=n;i++)        for(int j=1;j<=m;j++)            scanf("%d",&a[i][j]),S+=a[i][j];    int bh[4][2]={{1,0},{-1,0},{0,1},{0,-1}};    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        {            if((i+j)&1)            {                add(s,id(i,j),a[i][j]);                for(int k=0;k<4;k++)                {                    int x=i+bh[k][0],y=j+bh[k][1];                    if(x>=1&&x<=n&&y>=1&&y<=m)                        add(id(i,j),id(x,y),0x7fffffff);                }            }            else                add(id(i,j),t,a[i][j]);        }    }    printf("%d\n",S-dinic());    return 0;}

 

洛谷 P2774 方格取数问题