[BeiJing2006]狼抓兔子
Time Limit: ? 15 Sec?? Memory Limit: ? 162 MBSubmit: ? 1787?? Solved: ? 405
[ Submit ][ Status ][ Discuss ]
Description
現(xiàn)在小朋友們最喜歡的"喜羊羊與灰太狼",話說灰太狼抓羊不到，但抓兔子還是比較在行的，而且現(xiàn)在的兔子還比較笨，它們只有兩個(gè)窩，現(xiàn)在你做為狼王，面對下面這樣一個(gè)網(wǎng)格的地形：
?
?
左上角點(diǎn)為(1,1),右下角點(diǎn)為(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) 道路上的權(quán)值表示這條路上最多能夠通過的兔子數(shù)，道路是無向的. 左上角和右下角為兔子的兩個(gè)窩，開始時(shí)所有的兔子都聚集在左上角(1,1)的窩里，現(xiàn)在它們要跑到右下解(N,M)的窩中去，狼王開始伏擊這些兔子.當(dāng)然為了保險(xiǎn)起見，如果一條道路上最多通過的兔子數(shù)為K，狼王需要安排同樣數(shù)量的K只狼，才能完全封鎖這條道路，你需要幫助狼王安排一個(gè)伏擊方案，使得在將兔子一網(wǎng)打盡的前提下，參與的狼的數(shù)量要最小。因?yàn)槔沁€要去找喜羊羊麻煩.
Input
第一行為N,M.表示網(wǎng)格的大小，N,M均小于等于1000.接下來分三部分 第一部分共N行，每行M-1個(gè)數(shù)，表示橫向道路的權(quán)值. 第二部分共N-1行，每行M個(gè)數(shù)，表示縱向道路的權(quán)值. 第三部分共N-1行，每行M-1個(gè)數(shù)，表示斜向道路的權(quán)值. 輸入文件保證不超過10M
Output
輸出一個(gè)整數(shù)，表示參與伏擊的狼的最小數(shù)量.
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
?
?
注：具體轉(zhuǎn)化方法請看周冬大牛的2008年論文，好像是關(guān)于平面圖和最大流的關(guān)系。這個(gè)題目就是赤裸的最小割，但是邊數(shù)和點(diǎn)數(shù)大的驚人啊。只能轉(zhuǎn)化為平面圖最短路。但是我的程序并沒有ac這道題，但是參考其他人的程序并隨機(jī)化了幾組數(shù)據(jù)發(fā)現(xiàn)都可以通過，已經(jīng)查了好幾節(jié)課了終于放棄了。希望有大牛提供幾組容易錯(cuò)的數(shù)據(jù)。
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.
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
