建筑公司网站建设,交互设计英文,设计网络平台开发,网络营销案例分析实验报告3144: [Hnoi2013]切糕 Description Input 第一行是三个正整数P,Q,R#xff0c;表示切糕的长P、 宽Q、高R。第二行有一个非负整数D#xff0c;表示光滑性要求。接下来是R个P行Q列的矩阵#xff0c;第z个 矩阵的第x行第y列是v(x,y,z) (1≤x≤P, 1≤y≤Q, 1≤z≤R)。 100%的数据… 3144: [Hnoi2013]切糕 Description Input 第一行是三个正整数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≤400≤D≤R且给出的所有的不和谐值不超过1000。 Output 仅包含一个整数表示在合法基础上最小的总不和谐值。 Sample Input 2 2 2 1 6 1 6 1 2 6 2 6 Sample Output 6 HINT 最佳切面的f为f(1,1)f(2,1)2,f(1,2)f(2,2)1 恩。有个同学问我为什么连几条inf就能保证割边在范围之内我一下子语塞。过了很久才给了他答复他一下子欢喜极了。 另外需关注题意。我本来连了8个方向居然还懵了许久。 对了这是他的内容 这道题显然是一个网络流我们如果不考虑每次要切的相邻的范围的地方的话直接从每一竖列的下一层往上一层连边大概是这么个效果 对于切糕中的点我们以虚线的所示方法连边然后两边以INF的边连S和T显然跑一边最小割就可以了然而现在我们还要解决每次切的相邻的范围在d之内…这个对于我这个垃圾来说…简直是难题…然后我们可以这样连 我们从上往下建INF的边具体操作是如果可以就向周围的下面的竖直坐标相差为d的点建边这样一来为什么就可以保证割的边在范围之内呢我们看上面的图箭头为正向边的方向假如图中的A部分被我们割掉了现在如何才能保证左侧割掉的边一定在左侧的D区域呢首先我们感性认知一下现在还存在的路是C-D-B中间进过两条INF的边还有一条路可以增广也就是F-D-E这条路D同时在这两条路里如果只割一次那么只能割D 下一步我们看来思考为什么在两条路中各割一条会比在D中割一条不优…可能是我太智障了我思考这个图思考了好久233其实道理很简单啊观察这张图如果我们割掉三条长度为1的边我们能把图增广完嘛明显不是最小割嘛割都没割这里还有一条路嘛 也就是说你割外面的边而不割蓝色部分的边你割都没割到要点反而多花费了并且还是有路并且改路的最大流没有减少可以通过去也就是说图上还有一条经过蓝色边的路径可以被割并且在你割不在蓝色路径上的边之后并没有对这条还可以增广的路造成影响 这道题由朱爷分享代码如下 1 /**************************************************************2 Problem: 31443 User: Doggu4 Language: C5 Result: Accepted6 Time:1236 ms7 Memory:17652 kb8 ****************************************************************/9
10 #include cstdio
11 #include cstring
12 #include algorithm
13
14 templateclass Tinline void readin(T res) {
15 static char ch;T flag1;
16 while((chgetchar())0||ch9)if(ch-)flag-1;
17 resch-48;while((chgetchar())0ch9)res(res1)(res3)ch-48;res*flag;
18 }
19
20 const int N 100100;
21 const int M 1000010;
22 const int inf 0x3f3f3f3f;
23 const int dx[] {-1,1,0,0};
24 const int dy[] {0,0,-1,1};
25 struct Edge {int v, upre, cap, flow;}g[M];
26 int head[N], ne-1;
27 inline void adde(int u,int v,int cap) {
28 g[ne](Edge){v,head[u],cap,0};head[u]ne;
29 g[ne](Edge){u,head[v],0,0};head[v]ne;
30 }
31
32 #include queue
33 std::queueint q;
34 int n, m, H, dlt, x, s, t, d[N], cur[N];
35 bool BFS() {
36 memset(d,0,sizeof(d));
37 while(!q.empty()) q.pop();
38 q.push(s);d[s]1;
39 while(!q.empty()) {
40 int uq.front();q.pop();
41 for( int i head[u]; i!-1; i g[i].upre ) {
42 int vg[i].v;
43 if(g[i].capg[i].flow!d[v]) {q.push(v);d[v]d[u]1;}
44 }
45 }
46 return d[t]!0;
47 }
48 int DFS(int u,int a) {
49 if(ut||a0) return a;
50 int flow0, f;
51 for( int i cur[u]; i!-1; i g[i].upre ) {
52 int vg[i].v;
53 if(d[v]d[u]1(fDFS(v,std::min(a,g[i].cap-g[i].flow)))0) {
54 flowf;a-f;
55 g[i].flowf;g[i^1].flow-f;
56 if(a0) break;
57 }
58 }
59 if(flow0) d[u]0;
60 return flow;
61 }
62 int maxflow() {
63 int flow0;
64 while(BFS()) {
65 memcpy(cur,head,sizeof(head));
66 flowDFS(s,inf);
67 }
68 printf(%d\n,flow);
69 }
70 inline int pos(int i,int j,int h) {return (h-1)*n*m(i-1)*mj;}
71 int main() {
72 memset(head,-1,sizeof(head));
73 readin(n);readin(m);readin(H);readin(dlt);s0;t66000;
74 for( int i 1; i n; i ) for( int j 1; j m; j ) adde(s,pos(i,j,1),inf), adde(pos(i,j,H1),t,inf);
75 for( int i 1; i n; i ) for( int j 1; j m; j ) for( int h 1; h H1; h ) if(hdltH1)
76 for( int k 0; k 4; k ) if(1idx[k]idx[k]n1jdy[k]jdy[k]m) adde(pos(idx[k],jdy[k],hdlt),pos(i,j,h),inf);
77 for( int h 1; h H; h ) for( int i 1; i n; i ) for( int j 1; j m; j ) readin(x),adde(pos(i,j,h),pos(i,j,h1),x);
78 maxflow();
79 return 0;
80 }
81 dinic最小割建图1236 ms 17652 kb 对了其中最后一层可以压缩。 1 /**************************************************************2 Problem: 31443 User: Doggu4 Language: C5 Result: Accepted6 Time:1112 ms7 Memory:17652 kb8 ****************************************************************/9
10 #include cstdio
11 #include cstring
12 #include algorithm
13
14 templateclass Tinline void readin(T res) {
15 static char ch;T flag1;
16 while((chgetchar())0||ch9)if(ch-)flag-1;
17 resch-48;while((chgetchar())0ch9)res(res1)(res3)ch-48;res*flag;
18 }
19
20 const int N 100100;
21 const int M 1000010;
22 const int inf 0x3f3f3f3f;
23 const int dx[] {-1,1,0,0};
24 const int dy[] {0,0,-1,1};
25 struct Edge {int v, upre, cap, flow;}g[M];
26 int head[N], ne-1;
27 inline void adde(int u,int v,int cap) {
28 g[ne](Edge){v,head[u],cap,0};head[u]ne;
29 g[ne](Edge){u,head[v],0,0};head[v]ne;
30 }
31
32 #include queue
33 std::queueint q;
34 int n, m, H, dlt, x, s, t, d[N], cur[N];
35 bool BFS() {
36 memset(d,0,sizeof(d));
37 while(!q.empty()) q.pop();
38 q.push(s);d[s]1;
39 while(!q.empty()) {
40 int uq.front();q.pop();
41 for( int i head[u]; i!-1; i g[i].upre ) {
42 int vg[i].v;
43 if(g[i].capg[i].flow!d[v]) {q.push(v);d[v]d[u]1;}
44 }
45 }
46 return d[t]!0;
47 }
48 int DFS(int u,int a) {
49 if(ut||a0) return a;
50 int flow0, f;
51 for( int i cur[u]; i!-1; i g[i].upre ) {
52 int vg[i].v;
53 if(d[v]d[u]1(fDFS(v,std::min(a,g[i].cap-g[i].flow)))0) {
54 flowf;a-f;
55 g[i].flowf;g[i^1].flow-f;
56 if(a0) break;
57 }
58 }
59 if(flow0) d[u]0;
60 return flow;
61 }
62 int maxflow() {
63 int flow0;
64 while(BFS()) {
65 memcpy(cur,head,sizeof(head));
66 flowDFS(s,inf);
67 }
68 printf(%d\n,flow);
69 }
70 inline int pos(int i,int j,int h) {if(hH1) return t;return (h-1)*n*m(i-1)*mj;}
71 int main() {
72 memset(head,-1,sizeof(head));
73 readin(n);readin(m);readin(H);readin(dlt);s0;t66000;
74 for( int i 1; i n; i ) for( int j 1; j m; j ) adde(s,pos(i,j,1),inf);
75 for( int i 1; i n; i ) for( int j 1; j m; j ) for( int h 1; h H1; h ) if(hdltH1)
76 for( int k 0; k 4; k ) if(1idx[k]idx[k]n1jdy[k]jdy[k]m) adde(pos(idx[k],jdy[k],hdlt),pos(i,j,h),inf);
77 for( int h 1; h H; h ) for( int i 1; i n; i ) for( int j 1; j m; j ) readin(x),adde(pos(i,j,h),pos(i,j,h1),x);
78 maxflow();
79 return 0;
80 }
81 dinic最小割建图1112 ms 17652 kb 转载于:https://www.cnblogs.com/Doggu/p/BZOJ3144.html