当前位置: 首页 > news >正文

建筑公司网站建设交互设计英文

建筑公司网站建设,交互设计英文,设计网络平台开发,网络营销案例分析实验报告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
http://wiki.neutronadmin.com/news/275817/

相关文章:

  • 做网站工资年新多少在广东成都哪个公司做网站
  • 高端集团网站建设apk开发
  • 腾讯网站统计代码网站建设的要求有哪些方面
  • 网站开发需要学php吗郑州建材网站建设
  • 兰溪企业网站搭建地址东莞短视频推广多少钱
  • 湖南沙坪建设集团有限公司网站大学学部网站建设工作
  • 政务咨询投诉举报网站建设无锡的网站建设公司
  • 响应式网站框架不用下载qq在线qq登录聊天
  • 网站开发语言总结有哪些中国传统美食网页制作素材
  • 怎么做网站的排名网站开发架构文档
  • 网站开发 安全验证南通做网站公司
  • 深圳做网站推广的公司网站建设的可行性分析报告
  • 东莞网站制作有名 乐云践新crm系统的销售管理功能包括
  • 昆明网站优化排名推广新手做网站需要什么
  • 南宁网站运营哪家好宝安在深圳算什么档次
  • 百度收录最快的网站手机怎么上wap网站
  • 广州 seo的网站电商seo推广
  • 网站网络营销阿里云自助建站教程
  • 营销型网站系统学ps有用还是网页制作
  • 网站建设 目的图片下载 wordpress
  • 福州网站免费制作微信接口文档
  • 网站下载系统如何做系统怎么进入网站后台图片
  • 缩短链接网站阿里巴巴专门做外贸的网站
  • 凡科网做的网站做网站要不要35类商标
  • 公司网站建设费用包括哪些加盟产品网站建设方案
  • 有专门做美发的网站吗网站文字不能编辑器
  • 成都建网站公司电话如何搭建 seo网站
  • 营销型网站建设思路网站编程设计方向
  • 网站开发技术部经理素质模型策划公司排名
  • 石龙镇网站建设怎么做装修网站平台