二分匹配的灵活运用
3041还是比较好想的，考虑到横排/竖排射一枪就能搞定这一行/一列的所有点，
我们以行数为点集x，列数为点集y，在目标点(xi,yi)之间连一条边
这样最小射击次数=最小点覆盖（边两端点至少有一个点在覆盖集中）=最大匹配
poj2226是它的加强版
这里一块木板不能覆盖非泥泞点，也就是说一块木板不一定能搞定那一行所有的点
于是我们考虑到将连续的泥泞点标号，表示这些泥泞点是由哪个木板盖住（横竖分别标号）
这样，我们以横排木板为点集x，竖排木板为点集y，对于每个点，在盖住它的横竖排木板之间连边
（显然，每个点至多被一个横木板，一个竖木板覆盖）
于是根据poj3041，做匈牙利即可
var a:array[..,..] of char;
h1,h2:array[..,..] of longint;
map:array[..,..] of boolean;
cx,cy:array[..] of longint;
v:array[..] of boolean;
s1,s2,ans,i,j,n,m:longint; function find(x:longint):longint; //增广路
var i:longint;
begin
for i:= to s2 do
if map[x,i] and not v[i] then
begin
v[i]:=true;
if (cy[i]=-) or (find(cy[i])>) then
begin
cx[x]:=i;
cy[i]:=x;
exit();
end;
end;
exit();
end; begin
readln(n,m);
for i:= to n do
begin
for j:= to m do
begin
read(a[i,j]);
end;
readln;
end;
for i:= to n do //横排标号
begin
j:=;
while j<=m do
begin
if a[i,j]='*' then
begin
inc(s1);
h1[i,j]:=s1;
inc(j);
while a[i,j]='*' do
begin
h1[i,j]:=s1;
inc(j);
end;
end
else inc(j);
end;
end;
for i:= to m do //竖排标号
begin
j:=;
while j<=n do
begin
if a[j,i]='*' then
begin
inc(s2);
h2[j,i]:=s2;
inc(j);
while a[j,i]='*' do
begin
h2[j,i]:=s2;
inc(j);
end;
end
else inc(j);
end;
end;
for i:= to n do
for j:= to m do
map[h1[i,j],h2[i,j]]:=true; //连边
fillchar(cx,sizeof(cx),);
fillchar(cy,sizeof(cy),);
for i:= to s1 do //匈牙利
if cx[i]=- then
begin
fillchar(v,sizeof(v),false);
ans:=ans+find(i);
end;
writeln(ans);
end.
一定要注意问题建模的灵活运用；