[题目来源]：POJ3041
[关键字]：二分图最小点覆盖
[题目大意]：在一个坐标系中有k个障碍物，每次可以消除一整行或一整列上所有障碍物，问最少几次清除干净。
//=====================================================================================================
[分析]：利用行列法构造二分图：每个障碍物的x与y连一条边，此时每一条边就代表一个障碍物，而每一个点就代表一行或一列，所求即转化成了用最小的点覆盖所有的边=最小点覆盖=最大匹配。匈牙利算法求解。
[代码]：
View Code 1 var 2 n, k: longint; 3 map: array[0..1000,0..1000] of boolean; 4 b: array[0..1000] of boolean; 5 link: array[0..1000] of longint; 6 7 procedure init; 8 var 9 i, x, y: longint; 10 begin 11 readln(n,k); 12 fillchar(map,sizeof(map),false); 13 for i := 1 to k do 14 begin 15 readln(x,y); 16 map[x,y] := true; 17 end; 18 end; 19 20 function dfs(k: longint):boolean; 21 var 22 i: longint; 23 begin 24 for i := 1 to n do 25 if (map[k,i]) and (not b[i]) then 26 begin 27 b[i] := true; 28 if (link[i] = 0) or (dfs(link[i])) then 29 begin 30 link[i] := k; 31 exit(true); 32 end; 33 end; 34 exit(false); 35 end; 36 37 procedure work; 38 var 39 i, max: longint; 40 begin 41 max := 0; 42 for i := 1 to n do 43 begin 44 fillchar(b,sizeof(b),false); 45 if dfs(i) then inc(max); 46 end; 47 writeln(max); 48 end; 49 50 begin 51 init; 52 work; 53 end.