其实吧，bzoj2150还是比较水的，

在你知道什么是最小路径覆盖的前提下；

最小路径覆盖就是在有向无环图中，每个点只能被一条路径关联，问最少有多少条路能覆盖这个图

方法是，把对于原图每个点我们拆成左右两个点i1，i2，对于每条边i--->j，那么我们连i1，j2之间连一条边

然后就是二分图,ans=原图点数-最大匹配

这里总结一下很有用的结论

最小路径覆盖=原图点数-最大匹配

最大独立集=二分图总点数（左右两边）-最大匹配

最小顶点覆盖=最大匹配

回到这题上来，由于规定只能往下走，那么就保证了这是一个有向无环图

然后构造二分图求解即可

poj1422也是裸的最小路径覆盖，但被坑爹的读入格式WA了几次T T

poj1548比较水，不说了

1 type node=record 2        next,point:longint; 3      end; 4 var edge:array[0..1000010] of node; 5     a:array[0..60,0..60] of longint; 6     cx,cy,p:array[0..3000] of longint; 7     dx,dy:array[1..4] of longint; 8     v:array[0..3000] of boolean; 9     t,len,ans,i,j,k,n,m,r,c,x,y:longint;10     s:ansistring;11 12 procedure add(x,y:longint);13   begin14     inc(len);15     edge[len].point:=y;16     edge[len].next:=p[x];17     p[x]:=len;18   end;19 20 function find(x:longint):integer;21   var i,y:longint;22   begin23     i:=p[x];24     while i<>-1 do25     begin26       y:=edge[i].point;27       if not v[y] then28       begin29         v[y]:=true;30         if (cy[y]=-1) or (find(cy[y])=1) then31         begin32           cx[x]:=y;33           cy[y]:=x;34           exit(1);35         end;36       end;37       i:=edge[i].next;38     end;39     exit(0);40   end;41 42 begin43   readln(n,m,r,c);44   for i:=1 to n do45   begin46     readln(s);47     for j:=1 to m do48     begin49       if s[j]='.' then50       begin51         inc(t);52         a[i,j]:=t;53       end;54     end;55   end;56   dx[1]:=r; dx[2]:=r; dx[3]:=c; dx[4]:=c;57   dy[1]:=c; dy[2]:=-c; dy[3]:=r; dy[4]:=-r;58   fillchar(p,sizeof(p),-1);59   fillchar(cx,sizeof(cx),-1);60   fillchar(cy,sizeof(cy),-1);61   for i:=1 to n do62     for j:=1 to m do63       if a[i,j]<>0 then64         for k:=1 to 4 do65         begin66           x:=i+dx[k];67           y:=j+dy[k];68           if (x<=n) and (y>0) and (y<=m) and (a[x,y]>0) then add(a[i,j],a[x,y]);69         end;70 71   for i:=1 to t do72     if cx[i]=-1 then73     begin74       fillchar(v,sizeof(v),false);75       ans:=ans+find(i);76     end;77   writeln(t-ans);78 end.