江苏丹阳建设公司网站,鄂州正规网站建设,wordpress阅读权限插件,泰安房产网题目描述 现在小朋友们最喜欢喜羊羊与灰太狼,话说灰太狼抓羊不到#xff0c;但抓兔子还是比较在行的#xff0c;而且现在的兔子还比较笨#xff0c;它们只有两个窝#xff0c;现在你做为狼王#xff0c;面对下面这样一个网格的地形#xff1a;左上角点为(1,1… 题目描述 现在小朋友们最喜欢喜羊羊与灰太狼,话说灰太狼抓羊不到但抓兔子还是比较在行的而且现在的兔子还比较笨它们只有两个窝现在你做为狼王面对下面这样一个网格的地形 左上角点为(1,1),右下角点为(N,M)(上图中N3,M4).有以下三种类型的道路 1:(x,y)(x1,y) 2:(x,y)(x,y1) 3:(x,y)(x1,y1) 道路上的权值表示这条路上最多能够通过的兔子数道路是无向的。左上角和右下角为兔子的两个窝开始时所有的兔子都聚集在左上角(1,1)的窝里现在它们要跑到右下角(N,M)的窝中去狼王开始伏击这些兔子。当然为了保险起见如果一条道路上最多通过的兔子数为K狼王需要安排同样数量的K只狼才能完全封锁这条道路你需要帮助狼王安排一个伏击方案使得在将兔子一网打尽的前提下参与的狼的数量要最小。因为狼还要去找喜羊羊麻烦。 输入 第一行为N,M.表示网格的大小N,M均小于等于1000。 接下来分三部分 第一部分共N行每行M-1个数表示横向道路的权值。 第二部分共N-1行每行M个数表示纵向道路的权值。 第三部分共N-1行每行M-1个数表示斜向道路的权值。 输出 输出一个整数表示参与伏击的狼的最小数量。 样例输入 3 4 5 6 4 4 3 1 7 5 3 5 6 7 8 8 7 6 5 5 5 5 6 6 6 样例输出 14 题解 裸的最小割我转了转最大流跑Dinic。 记得连双向边。发现当前弧优化很优秀…… 1 #includecstdio2 #includecstring3 #define F(i,a,b) for(int ia;ib;i)4 #define F2(i,a,b) for(int ia;ib;i)5 #define v(a,b) ((a-1)*mb)6 int n,m,S,T;7 int h[1000001],nxt[6000001],to[6000001],cap[6000001],tot1;8 inline void ins(int x,int y,int c){nxt[tot]h[x];to[tot]y;cap[tot]c;h[x]tot;nxt[tot]h[y];to[tot]x;cap[tot]c;h[y]tot;}9 int iter[1000001],lv[1000001],que[1000001],l,r;
10 inline int Min(int p,int q){return pq?p:q;}
11 void init(){
12 int x;
13 scanf(%d%d,n,m); S1, Tv(n,m);
14 F(i,1,n) F2(j,1,m)
15 scanf(%d,x), ins(v(i,j),v(i,j1),x);
16 F2(i,1,n) F(j,1,m)
17 scanf(%d,x), ins(v(i,j),v(i1,j),x);
18 F2(i,1,n) F2(j,1,m)
19 scanf(%d,x), ins(v(i,j),v(i1,j1),x);
20 }
21 bool lvl(){
22 memset(lv,0,sizeof lv);
23 lv[S]1; que[1]S; lr1;
24 int u;
25 while(lr){
26 uque[l];
27 for(int ih[u];i;inxt[i])
28 if(cap[i]!lv[to[i]]) lv[to[i]]lv[u]1, que[r]to[i];
29 } if(!lv[T]) return 0;
30 F(i,S,T) iter[i]h[i];
31 return 1;
32 }
33 int flow(int u,int f){
34 if(uT) return f;
35 int d,sum0;
36 for(intiiter[u];i;inxt[i]){
37 if(cap[i]lv[to[i]]lv[u]){
38 dflow(to[i],Min(cap[i],f));
39 sumd; f-d;
40 cap[i]-d; cap[i^1]d;
41 if(!f) return sum;
42 }
43 }
44 return sum;
45 }
46 int Dinic(){
47 int sum0;
48 while(lvl())
49 sumflow(S,999999999);
50 return sum;
51 }
52 int main(){
53 init();
54 printf(%d,Dinic());
55 return 0;
56 } 转载于:https://www.cnblogs.com/PinkRabbit/p/7327131.html
