(二分图+最大流)洛谷P2774方格取数问题

news/2024/2/28 11:10:13

洛谷P2774方格取数问题

思路:

我们选取一格的时候,限制的是不能选取周围的四格。也就是说,我们可以考虑假设全选,然后删去不能选的格数的权值和的最小值,就可以得到能够选择所得到的最大值。
我们可以将点染成黑白两种颜色,对于点 ( i , j ) (i,j) (i,j),如果 ( i + j ) % 2 = 1 (i+j)\%2=1 (i+j)%2=1就为黑色,否则为白色。这样选择一个点的时候,就会对四周不同颜色的点造成影响。可以看出这是二分图带权最大独立集。二分图最大独立集=所有的点权-最小点覆盖数,又最小点覆盖=最大匹配。所以我们可以网络流求其最大流(最小割)。
建图:
对于黑色点 b i , j b_{i,j} bi,j建立 ( S , b i , j , a i , j ) (S,b_{i,j},a_{i,j}) (S,bi,j,ai,j)的边;对于白点 w i , j w_{i,j} wi,j建立 ( w i , j , T , a i , j ) (w_{i,j},T,a_{i,j}) (wi,j,T,ai,j)的边;对于黑点 b i , j b_{i,j} bi,j与四周的白点 w i ′ , j ′ w_{i^{'},j^{'}} wi,j建立 ( b i , j , w i ′ , j ′ , i n f ) (b_{i,j},w_{i^{'},j^{'}},inf) (bi,j,wi,j,inf)的边。

代码:

#include<bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define INF 1e18
const int N=1e6+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const double eps=1e-8;
const double pi=acos(-1);
using namespace std;
struct edge
{int u,v,w;
}e[N];
int head[N]={0},len=1,dis[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
void add(int u,int v,int w)
{e[++len]={head[u],v,w};head[u]=len;
}
void inc(int u,int v,int w)
{add(u,v,w);add(v,u,0);
}
int dep[N];
int dfs(int u,int f,int t)
{int ans=0,i;if(u==t)return f;for(i=head[u];i && f;i=e[i].u){int v=e[i].v,w=e[i].w;if(dep[v]==dep[u]+1 && w)//符合深度关系且能流 {int sum=dfs(v,min(f,w),t);e[i].w-=sum;e[i^1].w+=sum;f-=sum;ans+=sum;}	}if(!ans)dep[u]=-2;return ans;
}
int bfs(int s,int t)
{queue<int> q;cl(dep,0);dep[s]=1;//源点深度为1q.push(s);while(!q.empty()){int u=q.front(),i;q.pop();for(i=head[u];i;i=e[i].u){int v=e[i].v,w=e[i].w;if(w && !dep[v])//有深度且能流 {dep[v]=dep[u]+1;q.push(v); }}}return dep[t];
}
int dinic(int s,int t)
{int ans=0;while(bfs(s,t))ans+=dfs(s,inf,t);return ans;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m,i,j,k;cin>>m>>n;int s=0,t=m*n+1,res=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++){int x;cin>>x;res+=x;if((i+j)%2)inc(s,(i-1)*n+j,x);elseinc((i-1)*n+j,t,x);} for(i=1;i<=m;i++)for(j=1;j<=n;j++)if((i+j)%2){for(k=0;k<4;k++){int dx=i+dis[k][0],dy=j+dis[k][1];if(dx>=1 && dx<=m && dy>=1 && dy<=n)inc((i-1)*n+j,(dx-1)*n+dy,inf);}}res-=dinic(s,t);cout<<res<<endl;return 0;
}

http://www.ppmy.cn/news/168108.html

相关文章

CNN卷积神经网络

CNN是一种多层神经网络&#xff0c;基于人工神经网络&#xff0c;在人工神经网络前&#xff0c;用滤波器进行特征抽取&#xff0c;使用卷积核作为特征抽取器&#xff0c;自动训练特征抽取器&#xff0c;就是说卷积核以及阈值参数这些都需要由网络去学习。 图像可以直接作为网络…

linux上ssh免密登录原理及实现

因为我的服务器集群需要回收日志到中央进行统一处理&#xff0c;所以需要建立ssh互信关系实现免密登录。关于ssh的使用大家可能都很熟悉了&#xff0c;我们今天主要来讲下ssh连接和免密登录的原理。 scp 传输文件 scp(secure copy)是linux系统下基于ssh登录进行安全的远程文件拷…

关于 kubernetes网络(CNI规范)中Calico,NetworkPolicy(网络策略)方面的一些笔记

写在前面 学习k8s遇到整理笔记博文内容主要涉及K8s网络理论体系简述K8s中Calico网络方案容器跨主机通信过程DemoK8s中Calico的实现方案K8s中网络策略方式&#xff1a;egress和ingress的DemoipBlock,namespaceSelector,podSelector的网络策略规则Demo 认定一件事&#xff0c;即使…

牛客小白月赛24 (B、C、D、E、F、G、H、I、J)

比赛链接 B - 组队 思路&#xff1a;在排好序的能力值数组里面搞一个头指针&#xff0c;搞一个尾指针&#xff0c;如果尾部的能力值-头部的能力值在k之内&#xff0c;那么就让尾指针再往后移动&#xff0c;反之&#xff0c;记录当前尾部与头部的差值与答案取max&#xff0c;并…

【运筹学】线性规划数学模型 ( 单纯形法 | 第一次迭代 | 方程组同解变换 | 计算新单纯形表 | 计算检验数 | 入基变量选择 | 出基变量选择 )

文章目录 一、初始基可行解后第一次迭代二、迭代后新的单纯形表三、方程组同解变换四、生成新的单纯形表五、解出基可行解六、计算检验数 σ j \sigma_j σj​ 并选择入基变量七、计算 θ \theta θ 值并选择出基变量 上篇博客 【运筹学】线性规划数学模型 ( 单纯形法 | 迭代…

想知道聊天室系统是怎么做的吗?

昨天TJ君碰到一个小学的好友&#xff0c;聊起当年的种种过往&#xff0c;感慨一晃就那么多年过去了&#xff0c;唏嘘不已&#xff0c;其中有聊到聊天室&#xff0c;在那个没有微信没有各种交友APP的年代&#xff0c;聊天室可是大家交友的最佳之选。 TJ君的好友也算是半个程序猿…

Flink+Iceberg环境搭建及生产问题处理

全网最全大数据面试提升手册&#xff01; 概述 作为实时计算的新贵&#xff0c;Flink受到越来越多公司的青睐&#xff0c;它强大的流批一体的处理能力可以很好地解决流处理和批处理需要构建实时和离线两套处理平台的问题&#xff0c;可以通过一套Flink处理完成&#xff0c;降低…

linux上怎么实现ssh免密登录

这里直接写步骤,下面的有兴趣可以看看 1.进入到.ssh目录下 [rootwangjian /]# cd /root/.ssh/ [rootwangjian .ssh]# 2. 执行生成密钥&#xff0c;所有的参数都可以为空&#xff0c;也就是一直回车确认: ssh-keygen -t rsa [rootwangjian .ssh]# ssh-keygen -t rsa Generating…

【LED子系统深度剖析】八、小试牛刀

个人主页:董哥聊技术 我是董哥,高级嵌入式软件开发工程师,从事嵌入式Linux驱动开发和系统开发,曾就职于世界500强公司! 创作理念:专注分享高质量嵌入式文章,让大家读有所得! 文章目录 1、硬件管脚确定2、设备树配置3、子系统配置4、编译烧录5、验证5.1 设备树验证5.2 驱…

人工智能数学基础之线性代数(二)

前言 本文只会记录人工智能中所用到的线性代数知识&#xff0c;并不会记录大学线性代数教材中的所有知识。 现在CSDN不能发超长的文章了&#xff0c;只能分成多篇发布。 人工智能数学基础之线性代数(一) 人工智能数学基础之线性代数(二) 人工智能数学基础之线性代数(三) 行列…

华硕java安装教程win10_华硕电脑怎么安装win10?华硕电脑安装win10的图文教程

华硕电脑的性价比比较高&#xff0c;所以很多用户在购买电脑时都选择了这个品牌。现在有很多用户都喜欢使用win10系统&#xff0c;当新买的华硕电脑预装系统不是win10系统时&#xff0c;我们就需要给电脑重装系统了&#xff0c;那么具体应该怎么操作做呢&#xff1f;下面&#…

四阶代数余子式怎么求_已知四阶行列式,试求A41+A42与A43+A44,其中A4j(j=1,2,3,4)是D4中第4行第j个元素的代数余子式. - 搜题宝...

阅读理解&#xff1a;选择题 FREE MASSIVE ONLINE OPEN COURSES (MOOCS) A class with hundreds or even thousands of students might sound like a teachers worst nightmare. But a big idea in higher education these days is Massive Open Online Courses, or MOOCs. Som…

log4j2漏洞复现

log4j2漏洞复现 漏洞描述影响版本漏洞复现环境准备靶场搭建执行命令 修复建议 漏洞描述 Apache Log4j2是一款Java日志框架&#xff0c;是Log4j 的升级版。可以控制每一条日志的输出格式。通过定义每一条日志信息的级别&#xff0c;能够更加细致地控制日志的生成过程。 Apache …

ubuntu20安装xrdp以及解决黑屏问题

1、安装xrdp sudo apt-get install xrdp 2、将xrdp用户加入到如下用户组 sudo adduser xrdp ssl-cert 3、重启xrdp sudo service xrdp restart 4、打开windows远程面&#xff0c;连接&#xff0c;如果出现黑屏 sudo -s sudo vim /etc/xrdp/startwm.sh 加入如下内容&#xff…

Redis五大数据结构的底层实现

一)String类型:可以使用object encoding name就可以查看字符串的编码 SDS&#xff0c;flags的值不同&#xff0c;那么len和alloc所表示的值的数据范围也不同&#xff0c;所以flags的只是为了标识SDS头的总大小&#xff1b; alloc和len刚开始进行申请内存空间的时候都是相同的 S…

VS Code的launch.json配置文件如何编写?

文章目录 launch.jsonconfigurationsnametypelaunch.json {"version": "0.2.0","configurations": [{"name": "g++ - Build and debug active file"

NSS周常刷密码(2)

[GWCTF 2019]babyRSA 解答过程在脚本内 from Crypto.Util.number import * import gmpy2 import sympy import z3e 0x10001 N63658514959457474690903016018269086622290925646484729178300065183722792133723789965128794359777327094438403485892529574488072710160684141…

CAR-T药物|疗法适应症|市场销售-上市药品前景分析

对患有癌症的人来说&#xff0c;能够幸运地度过5年大关是一种成功&#xff0c;而能够成功地度过10年大关则是一种奇迹。Emily作为全球第一个接受CAR-T治疗成功的白血病儿童患者&#xff0c;至今已成功摆脱癌症11年之久。 ①CAR-T细胞治疗&#xff08;Emily Whitehead治疗案例时…

核心交换机、汇聚交换机、接入交换机

核心交换机 核心交换机是三层交换机支持路由功能&#xff0c;高速转发&#xff0c;有大容量接口宽带&#xff08;万兆&#xff09;&#xff0c;较大的背板出来能力&#xff0c;性能高于汇聚、接入交换机。 &#xff08;背板能力&#xff1a;背板能力是路由器的内部实现。背板能…

工业交换机与普通商用交换机区别

工业交换机&#xff0c;也称为工业以太网交换机&#xff0c;是一种专门设计用于工业环境的网络技术。它为工业网络提供可靠、高速的数据传输&#xff0c;包括速度更快的万兆(10G)工业交换机。通常&#xff0c;工业以太网是管理各种类型工业设备之间通信的一种经济有效的方法。 …
最新文章