网络流 方格取数类型题的总结 + HDU3820

2024-05-10 12:08

本文主要是介绍网络流 方格取数类型题的总结 + HDU3820,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目分析:最小割!

方格取数一类问题!

现在就这一类做一个小结吧。。。。

1.首先是方格内有固定的权值,可以取不相邻的数,问怎样取使权值最大。

这样我们奇偶建图,源点掌管奇属性点,汇点掌管偶属性点,然后相邻的两点建边容量无穷大,源汇向自己掌管的点建边,容量为权值。这样建图的意义在于,如果某一条边被割掉,那么久说明这个点被抛弃了(不选这个点),那么可不可能选到两个相邻的点?由于相邻两点的边为无穷大,那么这条边肯定不会被割掉,也就是说要么和源点相连的点被割掉,要么和汇点相连的被割掉!这样建图,被割掉一定是和源点或汇点相连的边,切记。结果是权值总和减去最小割。

两点间建边无穷大,可以这么认为,目的是为了最大化取的点是相邻点的代价,通过这种方式使得相邻两点必定不能同时取(否则这个代价太大)。


2.方格内有固定权值,可以取相邻的数,如果相邻的数被取走,那么需要付出一个这两个数同时被取走的代价,问怎样取使得权值最大。

同样奇偶建图,源汇分别和自己掌管的点建边,容量为权值。现在重点来了,因为可以同时取走相邻的点,那么我们相邻点之间就不能建边无穷大来约束了。其实约束条件其实就是相邻两点被取走的代价。怎么理解?如果同时取走两点的代价超过取走这两点带来的价值,那么说明这个方案不是最优的,因为显然我们可以只取其中一点。第一类问题其实就是通过将约束条件无穷大化来约束使得不能同时选择相邻的两点而已。


3.方格内有两种属性的权值,每个方格可以取其中一个属性的权值,可以取相邻的数,如果取走的相邻方格属于同一属性,需要花费相应的代价,问怎样取使得权值最大。

建图稍微不同:奇属性的格子的第一种属性和源点建边,第二种属性和汇点建边,容量为该属性在该格子对应的权值。偶属性的格子的第一种属性和汇点建边,第二种属性和源点建边,容量为该属性在该格子对应的权值。这样由于同一个格子我们只能取走其中一个属性的权值,那么对这两个属性建边无穷大约束一下就好。相邻两点取走相同属性怎么办?其实只要对该点的和源点相连的属性对相邻点的同一属性建边就行了(相邻点和该点同一属性则相邻点的该属性必定和汇点相连),约束条件就是代价。这样建图以后,每个点要么选取其中一个属性,要么都不选。


总结一下这一类问题,基本是奇偶建图,然后如果要求能取相邻点,那么相邻点建边,容量为代价,否则建边无穷大约束。建边无穷大可以约束两个条件使至多只能选取一个。


本题属于第三种情况。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<iomanip>
#include<queue>
#include<cmath>
#include<stack>
#include<map>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;
typedef long long LL;
const int int_max = 0x07777777;
const int int_min = 0x80000000;
const int maxn = 55*55*2;struct Edge{int from, to, cap, flow;Edge(int _from, int _to, int _cap, int _flow):from(_from),to(_to),cap(_cap),flow(_flow){}
};
vector<Edge> es;
vector<int> g[maxn];
int result,n,m,s,t,G,S;
int p[maxn],d[maxn],gap[maxn],cur[maxn],A[55][55],B[55][55];
void addedge (int from, int to, int cap){es.push_back(Edge(from, to, cap, 0));es.push_back(Edge(to, from, 0,0));int num = es.size();g[from].push_back(num-2);g[to].push_back(num-1);
}
void BFS (){queue<int> q;memset(d, 0, sizeof(d));d[t] = 0;q.push(t);while(!q.empty()){int u = q.front();q.pop();for(int i = 0; i < g[u].size(); i++){Edge& e = es[g[u][i]];if(e.cap==0 && d[e.to]==0){d[e.to] = d[u]+1;q.push(e.to);}}}
}
int augment (){int x = t;int a = int_max;while(x!=s){Edge& e = es[p[x]];a = (a < e.cap-e.flow ? a : e.cap-e.flow);x = es[p[x]].from;}x = t;while(x!=s){es[p[x]].flow += a;es[p[x]^1].flow -= a;x = es[p[x]].from;}return a;
}
int sap (){int flow = 0;BFS();memset(gap, 0, sizeof(gap));for(int i = 0; i <= t; i++) gap[d[i]]++;int x = s;memset(cur, 0, sizeof(cur));while(d[s] < t+1){if(x==t){flow += augment();x = s;}int ok = 0;for(int i = 0; i < g[x].size(); i++){Edge& e = es[g[x][i]];if(e.cap > e.flow && d[x]==d[e.to]+1){ok = 1;p[e.to] = g[x][i];cur[x] = i;x = e.to;break;}}if(!ok){int mm = t;for(int i = 0; i < g[x].size(); i++){Edge& e = es[g[x][i]];if(e.cap > e.flow) mm = (mm > d[e.to] ? d[e.to] : mm);}if(--gap[d[x]] == 0) break;gap[d[x]=mm+1]++;cur[x] = 0;if(x!=s) x = es[p[x]].from;}}return flow;
}int main(int argc, const char * argv[])
{int T;cin >> T;int count = 0;while(T--){scanf("%d %d %d %d", &n, &m, &G, &S);int total = 0;for(int i = 0; i < n; i++){for(int j = 0; j < m; j++) {scanf("%d", &A[i][j]);total += A[i][j];}}for(int i = 0; i < n; i++){for(int j = 0; j < m; j++) {scanf("%d", &B[i][j]);total += B[i][j];}}es.clear();s = n*m*2;t = s+1;int dir[4][2] = {-1,0,0,1,1,0,0,-1};for(int i = 0; i < maxn; i++) g[i].clear();for(int i = 0; i < n; i++){for(int j = 0; j < m; j++){if((i+j)%2==0){addedge(s, i*m+j, A[i][j]);addedge(i*m+j, i*m+j+n*m, int_max);addedge(i*m+j+n*m, t, B[i][j]);for(int u = 0; u < 4; u++){int ii = i + dir[u][0];int jj = j + dir[u][1];if(ii>=0 && ii<n && jj>=0 && jj<m){addedge(i*m+j, ii*m+jj, G);}}}else{addedge(s, i*m+j+n*m, B[i][j]);addedge(i*m+j+n*m, i*m+j, int_max);addedge(i*m+j, t, A[i][j]);for(int u = 0; u < 4; u++){int ii = i + dir[u][0];int jj = j + dir[u][1];if(ii>=0 && ii<n && jj>=0 && jj<m){addedge(i*m+j+n*m, ii*m+jj+n*m, S);}}}}}printf("Case %d: %d\n",++count,total-sap());}
}


这篇关于网络流 方格取数类型题的总结 + HDU3820的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/976395

相关文章

Java获取当前时间String类型和Date类型方式

《Java获取当前时间String类型和Date类型方式》:本文主要介绍Java获取当前时间String类型和Date类型方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录Java获取当前时间String和Date类型String类型和Date类型输出结果总结Java获取

Spring Boot 与微服务入门实战详细总结

《SpringBoot与微服务入门实战详细总结》本文讲解SpringBoot框架的核心特性如快速构建、自动配置、零XML与微服务架构的定义、演进及优缺点,涵盖开发环境准备和HelloWorld实战... 目录一、Spring Boot 核心概述二、微服务架构详解1. 微服务的定义与演进2. 微服务的优缺点三

SpringBoot改造MCP服务器的详细说明(StreamableHTTP 类型)

《SpringBoot改造MCP服务器的详细说明(StreamableHTTP类型)》本文介绍了SpringBoot如何实现MCPStreamableHTTP服务器,并且使用CherryStudio... 目录SpringBoot改造MCP服务器(StreamableHTTP)1 项目说明2 使用说明2.1

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys

Linux中压缩、网络传输与系统监控工具的使用完整指南

《Linux中压缩、网络传输与系统监控工具的使用完整指南》在Linux系统管理中,压缩与传输工具是数据备份和远程协作的桥梁,而系统监控工具则是保障服务器稳定运行的眼睛,下面小编就来和大家详细介绍一下它... 目录引言一、压缩与解压:数据存储与传输的优化核心1. zip/unzip:通用压缩格式的便捷操作2.

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,:本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta

SQL中JOIN操作的条件使用总结与实践

《SQL中JOIN操作的条件使用总结与实践》在SQL查询中,JOIN操作是多表关联的核心工具,本文将从原理,场景和最佳实践三个方面总结JOIN条件的使用规则,希望可以帮助开发者精准控制查询逻辑... 目录一、ON与WHERE的本质区别二、场景化条件使用规则三、最佳实践建议1.优先使用ON条件2.WHERE用

Nginx Location映射规则总结归纳与最佳实践

《NginxLocation映射规则总结归纳与最佳实践》Nginx的location指令是配置请求路由的核心机制,其匹配规则直接影响请求的处理流程,下面给大家介绍NginxLocation映射规则... 目录一、Location匹配规则与优先级1. 匹配模式2. 优先级顺序3. 匹配示例二、Proxy_pa

Android学习总结之Java和kotlin区别超详细分析

《Android学习总结之Java和kotlin区别超详细分析》Java和Kotlin都是用于Android开发的编程语言,它们各自具有独特的特点和优势,:本文主要介绍Android学习总结之Ja... 目录一、空安全机制真题 1:Kotlin 如何解决 Java 的 NullPointerExceptio

MySQL基本查询示例总结

《MySQL基本查询示例总结》:本文主要介绍MySQL基本查询示例总结,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Create插入替换Retrieve(读取)select(确定列)where条件(确定行)null查询order by语句li