经过千辛万苦小 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)。一个合法的切面满足以下两个条件:
输入格式:
第一行是三个正整数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 }