P3227 [HNOI2013]切糕

题目描述

经过千辛万苦小 A 得到了一块切糕,切糕的形状是长方体,小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑,小 A 希望切面能尽量光滑且和谐。于是她找到你,希望你能帮她找出最好的切割方案。

出于简便考虑,我们将切糕视作一个长 P、宽 Q、高 R 的长方体点阵。我们将位于第 z层中第 x 行、第 y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的点称为(x,y,z),它有一个非负的不和谐值 v(x,y,z)。一个合法的切面满足以下两个条件:

  1. 与每个纵轴(一共有 P*Q 个纵轴)有且仅有一个交点。即切面是一个函数 f(x,y),对于所有 1≤x≤P, 1≤y≤Q,我们需指定一个切割点 f(x,y),且 1≤f(x,y)≤R。
  2. 切面需要满足一定的光滑性要求,即相邻纵轴上的切割点不能相距太远。对于所有的 1≤x,x’≤P 和 1≤y,y’≤Q,若|x-x’|+|y-y’|=1,则|f(x,y)-f(x’,y’)| ≤D,其中 D 是给定的一个非负整数。 可能有许多切面f 满足上面的条件,小A 希望找出总的切割点上的不和谐值最小的那个。

输入输出格式

输入格式:

第一行是三个正整数P,Q,R,表示切糕的长P、 宽Q、高R。第二行有一个非负整数D,表示光滑性要求。接下来是R个P行Q列的矩阵,第z个 矩阵的第x行第y列是v(x,y,z) (1<=x<=P, 1<=y<=Q, 1<=z<=R)。 100%的数据满足P,Q,R<=40,0<=D<=R,且给出的所有的不和谐值不超过1000。

输出格式:

仅包含一个整数,表示在合法基础上最小的总不和谐值。

输入输出样例

输入样例#1:

2  2 2
1
6  1
6  1
2  6
2  6

输出样例#1:

6

说明

最佳切面的f为f(1,1)=f(2,1)=2,f(1,2)=f(2,2)=1

我们将点转化成边,那么选点就等于割边,第一个条件满足

对于第二个条件我们可以用一些inf的边来"屏蔽"那些不能割的边,从z向"相邻的"路径的z-d号点连inf的边(如上图)这样做之后,如果删了这条边,我们还可以通过这些桥梁,从相邻的路径的一段[z-d,z+d]绕过,所以割那些边就没有意义了

从而实现必须割[z-d,z+d]的目的

来源:洛谷题解

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<cmath>
  5 #include<queue>
  6 using namespace std;
  7 const int MAXN=200001;
  8 const int INF = 1e8;
  9 inline void read(int &n)
 10 {
 11     char c='+';int x=0;bool flag=0;
 12     while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}
 13     while(c>='0'&&c<='9'){x=x*10+c-48;c=getchar();}
 14     n=flag==1?-x:x;
 15 }
 16 int n,m,s,t;
 17 struct node
 18 {
 19     int u,v,flow,nxt;
 20 }edge[MAXN];
 21 int head[MAXN];
 22 int cur[MAXN];
 23 int num=0;
 24 int deep[MAXN];
 25 int tot=0;
 26 void add_edge(int x,int y,int z)
 27 {
 28     edge[num].u=x;
 29     edge[num].v=y;
 30     edge[num].flow=z;
 31     edge[num].nxt=head[x];
 32     head[x]=num++;
 33 }
 34 void add(int x,int y,int z)
 35 {
 36     add_edge(x,y,z);
 37     add_edge(y,x,0);
 38 }
 39 bool BFS()
 40 {
 41     memset(deep,0,sizeof(deep));
 42     deep[s]=1;
 43     queue<int>q;
 44     q.push(s);
 45     while(q.size()!=0)
 46     {
 47         int p=q.front();
 48         q.pop();
 49         for(int i=head[p];i!=-1;i=edge[i].nxt)
 50             if(!deep[edge[i].v]&&edge[i].flow)
 51                 deep[edge[i].v]=deep[edge[i].u]+1,
 52                 q.push(edge[i].v);
 53     }
 54     return deep[t];
 55     
 56 }
 57 int DFS(int now,int nowflow)
 58 {
 59     if(now==t||nowflow<=0)
 60         return nowflow;
 61     int totflow=0;
 62     for(int &i=cur[now];i!=-1;i=edge[i].nxt)
 63     {
 64         if(deep[edge[i].v]==deep[edge[i].u]+1&&edge[i].flow)
 65         {
 66             int canflow=DFS(edge[i].v,min(nowflow,edge[i].flow));
 67             edge[i].flow-=canflow;
 68             edge[i^1].flow+=canflow;
 69             totflow+=canflow;
 70             nowflow-=canflow;
 71             if(nowflow<=0)
 72                 break;
 73         }
 74     
 75     }
 76     return totflow;
 77 }
 78 void Dinic()
 79 {
 80     int ans=0;
 81     while(BFS())
 82     {
 83         memcpy(cur,head,MAXN);
 84         ans+=DFS(s,1e8);
 85     }
 86     printf("%d",ans);
 87 }
 88 int a[41][41][41];
 89 int cnt=0;
 90 int xx[5]={-1,+1,0,0};
 91 int yy[5]={0,0,-1,+1};
 92 int main()
 93 {
 94     memset(head,-1,sizeof(head));
 95     int P,Q,R,D;
 96     read(P);read(Q);read(R);read(D);
 97     for(int i=1;i<=R+1;i++)
 98         for(int j=1;j<=P;j++)
 99             for(int k=1;k<=Q;k++)
100                 a[i][j][k]=++cnt;
101     s=0;t=cnt+1;
102     for(int i=1;i<=P;i++)
103         for(int j=1;j<=Q;j++)
104         {
105             add(s,a[1][i][j],INF);
106             add(a[R+1][i][j],t,INF);//上下界 
107         }
108     for(int i=1;i<=R;i++)
109         for(int j=1;j<=P;j++)
110             for(int k=1;k<=Q;k++)
111             {
112                 int p;read(p);
113                 add(a[i][j][k],a[i+1][j][k],p);
114             }// 连边 
115     for(int i=D+1;i<=R;i++)
116         for(int j=1;j<=P;j++)
117             for(int k=1;k<=Q;k++)
118                 for(int m=0;m<4;m++)
119                     if(a[i-D][j+xx[m]][k+yy[m]]>0)
120                         add(a[i][j][k],a[i-D][j+xx[m]][k+yy[m]],INF);
121     //for(int i=1;i<=num-1;i++)
122     //printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].flow);
123     Dinic();
124     return  0;
125 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Linyb极客之路

UML类图(下):关联、聚合、组合、依赖

关联(Assocition)关系是类与类之间最常见的一种关系,它是一种结构化的关系,表示一类对象与另一类对象之间有联系,如汽车和轮胎、师傅和徒弟、班级和学生等。...

1572
来自专栏从零开始学自动化测试

python笔记1-用python解决小学生数学题

前几天有人在群里给小编出了个数学题: 假设你有无限数量的邮票,面值分别为6角,7角,8角,请问你最大的不可支付邮资是多少元? 小编掰着手指头和脚趾头算了下,答案...

3419
来自专栏数据结构与算法

BZOJ3693: 圆桌会议(Hall定理 线段树)

我的思路:对于区间分两种情况讨论,一种是完全包含,另一种是部分包含。 第一种情况非常好判断,至于计算对于一个区间[l, r]的$\sum a[i]$就可以了,但...

1062
来自专栏JadePeng的技术博客

知识图谱学习笔记(1)

4205
来自专栏ACM算法日常

2018南京大学计算机夏令营机试题

lipper同学问了我一个算法题,由于时间原因没来得及写,lipper同学就自己动手写了出来,并且顺手写了此篇博文,文笔潇洒,与君共勉。

6761
来自专栏racaljk

Leetcode 70. Climbing Stairs 爬楼梯 (递归,记忆化,动态规划)

在第0阶,可以选择走到第1阶或者第2阶,第1阶可以走第2阶或者第3阶,第二阶可以走第3阶或者第4阶...。如此继续就生成了上图递归解答树。注意如果直接递归会超时...

3503
来自专栏沈唁志

BC数学函数:PHP处理有关钱数等浮点数计算时高精确度函数库

在商城类的项目当中,避免不了钱数的计算,也就会出现所谓的浮点数精度问题,前两天阅文的小哥哥面试我的时候就问到了这个,Mysql怎么去存钱数?PHP又该怎么处理浮...

1022
来自专栏数据结构与算法

P1823 音乐会的等待

题目描述 N个人正在排队进入一个音乐会。人们等得很无聊,于是他们开始转来转去,想在队伍里寻找自己的熟人。队列中任意两个人A和B,如果他们是相邻或他们之间没有人比...

39513
来自专栏小樱的经验随笔

51Nod 1016 水仙花数 V2(组合数学,枚举打表法)

1016 水仙花数 V2 基准时间限制:1 秒 空间限制:131072 KB 分值: 160         难度:6级算法题 水仙花数是指一个 n 位数 ...

2927
来自专栏web编程技术分享

来谈谈JAVA面向对象 - 继续说多态~

2985

扫码关注云+社区

领取腾讯云代金券