其实吧，bzoj2150还是比较水的，
在你知道什么是最小路径覆盖的前提下；
最小路径覆盖就是在有向无环图中，每个点只能被一条路径关联，问最少有多少条路能覆盖这个图
方法是，把对于原图每个点我们拆成左右两个点i1，i2，对于每条边i--->j，那么我们连i1，j2之间连一条边
然后就是二分图,ans=原图点数-最大匹配
这里总结一下很有用的结论
最小路径覆盖=原图点数-最大匹配
最大独立集=二分图总点数（左右两边）-最大匹配
最小顶点覆盖=最大匹配
回到这题上来，由于规定只能往下走，那么就保证了这是一个有向无环图
然后构造二分图求解即可
poj1422也是裸的最小路径覆盖，但被坑爹的读入格式WA了几次T T
poj1548比较水，不说了
type node=record
next,point:longint;
end;
var edge:array[..] of node;
a:array[..,..] of longint;
cx,cy,p:array[..] of longint;
dx,dy:array[..] of longint;
v:array[..] of boolean;
t,len,ans,i,j,k,n,m,r,c,x,y:longint;
s:ansistring; procedure add(x,y:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].next:=p[x];
p[x]:=len;
end; function find(x:longint):integer;
var i,y:longint;
begin
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
v[y]:=true;
if (cy[y]=-) or (find(cy[y])=) then
begin
cx[x]:=y;
cy[y]:=x;
exit();
end;
end;
i:=edge[i].next;
end;
exit();
end; begin
readln(n,m,r,c);
for i:= to n do
begin
readln(s);
for j:= to m do
begin
if s[j]='.' then
begin
inc(t);
a[i,j]:=t;
end;
end;
end;
dx[]:=r; dx[]:=r; dx[]:=c; dx[]:=c;
dy[]:=c; dy[]:=-c; dy[]:=r; dy[]:=-r;
fillchar(p,sizeof(p),-);
fillchar(cx,sizeof(cx),-);
fillchar(cy,sizeof(cy),-);
for i:= to n do
for j:= to m do
if a[i,j]<> then
for k:= to do
begin
x:=i+dx[k];
y:=j+dy[k];
if (x<=n) and (y>) and (y<=m) and (a[x,y]>) then add(a[i,j],a[x,y]);
end; for i:= to t do
if cx[i]=- then
begin
fillchar(v,sizeof(v),false);
ans:=ans+find(i);
end;
writeln(t-ans);
end.
bzoj2150