【ZOJ】2539 Energy Minimization 最小割——项目分配问题

2024-09-05 15:18

本文主要是介绍【ZOJ】2539 Energy Minimization 最小割——项目分配问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

传送门:【ZOJ】2539 Energy Minimization


题目分析:还是项目分配问题,还是曾经的味道TUT

再次请出神奇的函数:


再看看题目中的函数:

惊人的相似啊有木有!简直就是稍作修改就好了。。

因为Xi只能取0或1,所以最终我们可以将所有的Xi分成两个集合:Xi取1的集合,Xi取0的集合。

假设源点S和Xi取1的集合相连,汇点T和Xi取0的集合相连。

一开始,我们先将所有的Xi和源点S以及汇点T相连,表示Xi的取值还未确定。

由公式可知Xi选择1会产生ai的花费,Xi选择0会产生bi的花费,Xi和Xj的选择不同会产生cij的花费。

如果Xi取0,也就是说Xi不可以取1,那么需要割掉Xi->T的边,因为割掉Xi->T的代价为| pi - v0 |,所以Xi->T的边容量为| pi - v0 |。

如果Xi取1,也就是说Xi不可以取0,那么需要割掉S->Xi的边,因为割掉S->Xi的代价为| pi - v1 |,所以S->Xi的边容量为| pi - v1 |。

现在,如果Xi取1,Xj取0,因为i,j不能同属一个集合,所以还需要割掉i->j,由上式可知,割掉i->j的边会产生| pi - pj |的代价,所以i->j的边容量为| pi - pj |这里j是在i上下左右的点。

最后跑一遍最小割即可得到该函数的最小值。


代码如下:


#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;#define REP( i , a , b ) for ( int i = a ; i < b ; ++ i )
#define REV( i , a , b ) for ( int i = a - 1 ; i >= b ; -- i )
#define FOR( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define FOV( i , a , b ) for ( int i = a ; i >= b ; -- i )
#define CLR( a , x ) memset ( a , x , sizeof a )
#define CPY( a , x ) memcpy ( a , x , sizeof a )typedef long long LL ;
typedef int type_c ;
typedef int type_f ;const int MAXN = 405 ;
const int MAXQ = 405 ;
const int MAXE = 23333 ;
const int INF = 0x3f3f3f3f ;struct Edge {int v , n ;type_c c , rc ;Edge () {}Edge ( int v , type_c c , int n ) : v ( v ) , c ( c ) , n ( n ) {}
} ;struct Net {Edge E[MAXE] ;int H[MAXN] , cntE ;int d[MAXN] , cur[MAXN] , pre[MAXN] , num[MAXN] ;int Q[MAXQ] , head , tail ;int s , t , nv ;type_f flow ;int n ;int G[20][20] ;void init () {cntE = 0 ;CLR ( H , -1 ) ;}void addedge ( int u , int v , type_c c , type_c rc = 0 ) {E[cntE] = Edge ( v ,  c , H[u] ) ;H[u] = cntE ++ ;E[cntE] = Edge ( u , rc , H[v] ) ;H[v] = cntE ++ ;}void rev_bfs () {CLR ( d , -1 ) ;CLR ( num , 0 ) ;head = tail = 0 ;Q[tail ++] = t ;d[t] = 0 ;num[d[t]] = 1 ;while ( head != tail ) {int u = Q[head ++] ;for ( int i = H[u] ; ~i ; i = E[i].n ) {int v = E[i].v ;if ( d[v] == -1 ) {Q[tail ++] = v ;d[v] = d[u] + 1 ;num[d[v]] ++ ;}}}}type_f ISAP () {CPY ( cur , H ) ;rev_bfs () ;flow = 0 ;int u = pre[s] = s , i , pos , mmin ;while ( d[s] < nv ) {if ( u == t ) {type_f f = INF ;for ( i = s ; i != t ; i = E[cur[i]].v )if ( f > E[cur[i]].c ) {f = E[cur[i]].c ;pos = i ;}for ( i = s ; i != t ; i = E[cur[i]].v ) {E[cur[i]].c -= f ;E[cur[i] ^ 1].c += f ;}u = pos ;flow += f ;}for ( i = cur[u] ; ~i ; i = E[i].n )if ( E[i].c && d[u] == d[E[i].v] + 1 )break ;if ( ~i ) {cur[u] = i ;pre[E[i].v] = u ;u = E[i].v ;}else {if ( 0 == -- num[d[u]] )break ;for ( mmin = nv , i = H[u] ; ~i ; i = E[i].n )if ( E[i].c && mmin > d[E[i].v] ) {mmin = d[E[i].v] ;cur[u] = i ;}d[u] = mmin + 1 ;num[d[u]] ++ ;u = pre[u] ;}}return flow ;}void solve () {int R , C , v0 , v1 ;scanf ( "%d%d%d%d" , &R , &C , &v0 , &v1 ) ;n = R * C ;init () ;s = n , t = n + 1 , nv = t + 1 ;REP ( i , 0 , R )REP ( j , 0 , C ) {scanf ( "%d" , &G[i][j] ) ;addedge ( s , i * C + j , abs ( G[i][j] - v1 ) ) ;addedge ( i * C + j , t , abs ( G[i][j] - v0 ) ) ;}REP ( i , 0 , R )REP ( j , 0 , C ) {int ij = i * C + j ;if ( i < R - 1 )addedge ( ij , ij + C , abs ( G[i][j] - G[i + 1][j] ) , abs ( G[i][j] - G[i + 1][j] ) ) ;if ( j < C - 1 )addedge ( ij , ij + 1 , abs ( G[i][j] - G[i][j + 1] ) , abs ( G[i][j] - G[i][j + 1] ) ) ;}printf ( "%d\n" , ISAP () ) ;}
} e ;int main () {int T , cas = 0 ;scanf ( "%d" , &T ) ;while ( T -- ) {printf ( "Case %d:\n" , ++ cas ) ;e.solve () ;if ( T )printf ( "\n" ) ;}return 0 ;
}


这篇关于【ZOJ】2539 Energy Minimization 最小割——项目分配问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1139318

相关文章

SpringBoot内嵌Tomcat临时目录问题及解决

《SpringBoot内嵌Tomcat临时目录问题及解决》:本文主要介绍SpringBoot内嵌Tomcat临时目录问题及解决,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录SprinjavascriptgBoot内嵌Tomcat临时目录问题1.背景2.方案3.代码中配置t

SpringBoot使用GZIP压缩反回数据问题

《SpringBoot使用GZIP压缩反回数据问题》:本文主要介绍SpringBoot使用GZIP压缩反回数据问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot使用GZIP压缩反回数据1、初识gzip2、gzip是什么,可以干什么?3、Spr

将Java项目提交到云服务器的流程步骤

《将Java项目提交到云服务器的流程步骤》所谓将项目提交到云服务器即将你的项目打成一个jar包然后提交到云服务器即可,因此我们需要准备服务器环境为:Linux+JDK+MariDB(MySQL)+Gi... 目录1. 安装 jdk1.1 查看 jdk 版本1.2 下载 jdk2. 安装 mariadb(my

如何解决idea的Module:‘:app‘platform‘android-32‘not found.问题

《如何解决idea的Module:‘:app‘platform‘android-32‘notfound.问题》:本文主要介绍如何解决idea的Module:‘:app‘platform‘andr... 目录idea的Module:‘:app‘pwww.chinasem.cnlatform‘android-32

Node.js 数据库 CRUD 项目示例详解(完美解决方案)

《Node.js数据库CRUD项目示例详解(完美解决方案)》:本文主要介绍Node.js数据库CRUD项目示例详解(完美解决方案),本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考... 目录项目结构1. 初始化项目2. 配置数据库连接 (config/db.js)3. 创建模型 (models/

kali linux 无法登录root的问题及解决方法

《kalilinux无法登录root的问题及解决方法》:本文主要介绍kalilinux无法登录root的问题及解决方法,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,... 目录kali linux 无法登录root1、问题描述1.1、本地登录root1.2、ssh远程登录root2、

SpringBoot应用中出现的Full GC问题的场景与解决

《SpringBoot应用中出现的FullGC问题的场景与解决》这篇文章主要为大家详细介绍了SpringBoot应用中出现的FullGC问题的场景与解决方法,文中的示例代码讲解详细,感兴趣的小伙伴可... 目录Full GC的原理与触发条件原理触发条件对Spring Boot应用的影响示例代码优化建议结论F

springboot项目中常用的工具类和api详解

《springboot项目中常用的工具类和api详解》在SpringBoot项目中,开发者通常会依赖一些工具类和API来简化开发、提高效率,以下是一些常用的工具类及其典型应用场景,涵盖Spring原生... 目录1. Spring Framework 自带工具类(1) StringUtils(2) Coll

MySQL 中查询 VARCHAR 类型 JSON 数据的问题记录

《MySQL中查询VARCHAR类型JSON数据的问题记录》在数据库设计中,有时我们会将JSON数据存储在VARCHAR或TEXT类型字段中,本文将详细介绍如何在MySQL中有效查询存储为V... 目录一、问题背景二、mysql jsON 函数2.1 常用 JSON 函数三、查询示例3.1 基本查询3.2

Pyserial设置缓冲区大小失败的问题解决

《Pyserial设置缓冲区大小失败的问题解决》本文主要介绍了Pyserial设置缓冲区大小失败的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面... 目录问题描述原因分析解决方案问题描述使用set_buffer_size()设置缓冲区大小后,buf