亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

BJOI[beijing]2006 狼抓兔子

系統 1806 0

[BeiJing2006]狼抓兔子

Time Limit: ? 15 Sec?? Memory Limit: ? 162 MB
Submit: ? 1787?? Solved: ? 405
[ Submit ][ Status ][ Discuss ]

Description

現在小朋友們最喜歡的"喜羊羊與灰太狼",話說灰太狼抓羊不到,但抓兔子還是比較在行的,而且現在的兔子還比較笨,它們只有兩個窩,現在你做為狼王,面對下面這樣一個網格的地形: ? ? 左上角點為(1,1),右下角點為(N,M)(上圖中N=4,M=5).有以下三種類型的道路 1:(x,y)<==>(x+1,y) 2:(x,y)<==>(x,y+1) 3:(x,y)<==>(x+1,y+1) 道路上的權值表示這條路上最多能夠通過的兔子數,道路是無向的. 左上角和右下角為兔子的兩個窩,開始時所有的兔子都聚集在左上角(1,1)的窩里,現在它們要跑到右下解(N,M)的窩中去,狼王開始伏擊這些兔子.當然為了保險起見,如果一條道路上最多通過的兔子數為K,狼王需要安排同樣數量的K只狼,才能完全封鎖這條道路,你需要幫助狼王安排一個伏擊方案,使得在將兔子一網打盡的前提下,參與的狼的數量要最小。因為狼還要去找喜羊羊麻煩.

Input

第一行為N,M.表示網格的大小,N,M均小于等于1000.接下來分三部分 第一部分共N行,每行M-1個數,表示橫向道路的權值. 第二部分共N-1行,每行M個數,表示縱向道路的權值. 第三部分共N-1行,每行M-1個數,表示斜向道路的權值. 輸入文件保證不超過10M

Output

輸出一個整數,表示參與伏擊的狼的最小數量.

Sample Input

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

Sample Output

14
?
?
注:具體轉化方法請看周冬大牛的2008年論文,好像是關于平面圖和最大流的關系。這個題目就是赤裸的最小割,但是邊數和點數大的驚人啊。只能轉化為平面圖最短路。但是我的程序并沒有ac這道題,但是參考其他人的程序并隨機化了幾組數據發現都可以通過,已經查了好幾節課了終于放棄了。希望有大牛提供幾組容易錯的數據。
                        type  

  ji=^rec;

  rec=record

  data,v:longint;

  next:ji;

end;



var

  a:array[0..2000000] of ji;

  v:array[0..2000000] of boolean;

  d:array[0..2000000] of int64;

  q:array[0..3000000] of longint;

  h:array[0..1001,0..1001,0..1] of longint;

  i,j,k,m,n,vv,vs,vt:longint;



procedure spfa;

var

  p:ji;

  s,t,head,tail,i,now:longint;

begin

  fillchar(d,sizeof(d),30);

  fillchar(v,sizeof(v),0);

  fillchar(q,sizeof(q),0);

  d[vs]:=0; v[vs]:=true; q[1]:=vs;

  head:=1; tail:=1; s:=1; t:=1;

  while s<=t do

    begin

	  now:=q[head];

	  p:=a[now];

	  while p<>nil do

	    begin

		  i:=p^.data;

		  if d[i]>d[now]+p^.v then 

		    begin

			  d[i]:=d[now]+p^.v;

			  if not v[i] then

			    begin

				  inc(tail); inc(t);

				  if tail>3000000 then tail:=1;

				  q[tail]:=i;

				  v[i]:=true;

				end;

			end;

		  p:=p^.next;

		end;

	  inc(head); inc(s);

	  if head>3000000 then head:=1;

	  v[now]:=false;

	end;

end;



procedure insert(x,y,w:longint);

var

  p:ji;

begin 

  new(p); p^.data:=y; p^.v:=w; p^.next:=a[x]; a[x]:=p;

  new(p); p^.data:=x; p^.v:=w; p^.next:=a[y]; a[y]:=p; 

end;



begin

  readln(n,m); vv:=0;

  for i:=1 to n-1 do

    for j:=1 to m-1 do

	  for k:=0 to 1 do 

	    begin

		  inc(vv);

		  h[i,j,k]:=vv;

		end;

  fillchar(a,sizeof(a),0);

  vs:=vv+1; vt:=vs+1;

  for i:=1 to m-1 do

    begin

	  read(k);

	  insert(vs,h[1,i,0],k);

	end;

  for i:=1 to n-2 do

    for j:=1 to m-1 do

	  begin

	    read(k);

		insert(h[i,j,1],h[i+1,j,0],k);

	  end;

  for i:=1 to m-1 do

    begin 

	  read(k);

	  insert(h[n-1,i,1],vt,k);

	end;

  for i:=1 to n-1 do

    begin

	  read(k); insert(h[i,1,1],vt,k);

	  for j:=1 to m-2 do

	    begin

		  read(k);

		  insert(h[i,j,0],h[i,j+1,1],k);

		end;

	  read(k); insert(vs,h[i,m-1,0],k);

	end;

  for i:=1 to n-1 do 

    for j:=1 to m-1 do

	  begin

	    read(k);

	    insert(h[i,j,0],h[i,j,1],k);

	  end;

  spfa;

  writeln(d[vt]);

end.


                      

BJOI[beijing]2006 狼抓兔子


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 亚洲一区高清 | 亚洲国产成人久久综合一区77 | 久久久久久久综合日本亚洲 | 亚洲国产欧美精品 | 国产男女爽爽爽免费视频 | 999久久久国产精品 999久久久精品视频在线观看 | 国产一区中文字幕 | 夜夜操com| 国产午夜偷精品偷伦 | 狠狠色噜噜狠狠狠狠97影音先锋 | 免费视频一区二区性色 | 天然素人在线观看 | 在线观看日韩精品 | 成人一级免费视频 | 欧美曰韩一区二区三区 | 伊人网综合在线观看 | 国产成人99精品免费观看 | 久久久精品波多野结衣 | 国产精品品福利视频 | 日本久久高清视频 | 91九色首页 | 久久九九99热这里只有精品 | 69性影院在线观看国产精品87 | 婷婷综合视频 | 精品国产免费观看 | 国产国产精品人在线观看 | 亚洲欧洲一区二区三区在线观看 | 亚洲精品乱码久久久久久麻豆 | 久久99国产乱子伦精品免 | 欧美在线一区二区三区精品 | 点击进入不卡毛片免费观看 | xx色综合 | 嘿咻成人免费视频欧美激情 | 中国性猛交xxxxx免费看 | 妖精视频在线看免费视频 | 男女羞羞视频免费观看 | 奇米第九色 | 久久午夜影院 | 欧美巨大xxxx做受孕妇视频 | 国产免费不卡v片在线观看 国产免费不卡视频 | 久久精品亚洲综合一品 |