[BeiJing2006]狼抓兔子
Time Limit: ? 15 Sec?? Memory Limit: ? 162 MBSubmit: ? 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
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.
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

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