行列覆盖，最小点集覆盖

【题目】：Muddy Fields 【类型】：图论 【难度】：3 【来源】：PKU 2226 【关键字】：二分图匹配 行列【题目】：Muddy Fields 【类型】：图论 【难度】：3 【来源】：PKU 2226 【关键字】：二分图匹配 行列覆盖 最小点集覆盖

【题目大意】：N行M列的地，*代表泥地，.代表草地。你必须用宽为1，长度不限的木板将泥地覆盖住，且不能覆盖草地。问最少需要几块木板。

【分析】：

如果是普通的行列覆盖，则我们将行作为元素，将列作为元素，进行二分图匹配，即可求出行列覆盖。

但是，若不能覆盖到草地。我们则需要重新构图。

原来的构图是将整行整列作为元素，那么加入限制后，我们可以将每一行连通的块作为元素，先进行标号，再按原来的方式进行构图即可。

【时间复杂度】：O（N^2*M^2） 覆盖 最小点集覆盖

【题目大意】：N行M列的地，*代表泥地，.代表草地。你必须用宽为1，长度不限的木板将泥地覆盖住，且不能覆盖草地。问最少需要几块木板。

【分析】：

如果是普通的行列覆盖，则我们将行作为元素，将列作为元素，进行二分图匹配，即可求出行列覆盖。

但是，若不能覆盖到草地。我们则需要重新构图。

原来的构图是将整行整列作为元素，那么加入限制后，我们可以将每一行连通的块作为元素，先进行标号，，再按原来的方式进行构图即可。

【时间复杂度】：O（N^2*M^2）

var n,m,ans,tot1,tot2:longint;a:array[0..maxn,0..maxn] of boolean;g:array[0..maxm,0..maxm] of boolean;row,col:array[0..maxn,0..maxn] of longint;v:array[0..maxm] of boolean;link:array[0..maxm] of longint;:boolean; {匈牙利算法}var i:longint;tot2 v[i]:=true; if (link[i]=0)or(find(link[i])) then begin link[i]:=x; exit(true); end; end; exit(false);end;; {读入，构图}var i,j:longint;ch:char;begin readln(n,m); j:=(ch); a[i,j]:=ch=’*’; end; readln; end; tot1:=n j:=a[i,j] (j=1)or(not a[i,j-1]) then inc(tot1); row[i,j]:=tot1; end; end; tot2:=m i:=a[i,j] (i=1)or(not a[i-1,j]) then inc(tot2); col[i,j]:=tot2; end; end; j:=1 to m do g[row[i,j],col[i,j]]:=true;end;; {主函数}var i:longint;begin fillchar(link,sizeof(link),0); ans:=0; fillchar(v,sizeof(v),false); find(i); end; link[i]<>0 then inc(ans); writeln(ans); {输出}end;//=================================================================begin assign(input,’p2226.in’); reset(input); assign(output,’p2226.out’); rewrite(output); init; main; end; close(input); close(output);end.

当一个人真正觉悟的一刻，他放弃追寻外在世界的财富，