二分图最小覆盖：找到一个点集，使得每条边上至少有一个点在该集合中。

证明二分图最小覆盖=二分图最大匹配：

二分图最大匹配后，每个点都不能找到增广路，而找不到增广路的原因就是至少有一个点已经被匹配了。即这个点在二分图的最大匹配中。而二分图最大匹配中会存在同一条边两个点都在这个点集中的情况，我们只要取一个点即可。

 

本题当中，将机器A上的模式看作X集合，机器B上的模式看作Y集合，每个任务对应一条边，两点分别为在A，B上的模式，建立二分图。可以看出，最小的重新启动次数就是二分图的最小覆盖——即最大匹配。普通匈牙利算法即可。

Hint：注意一点：读入时要加上这样一句话，否则会WA：

if p*q=0 then continue;

 

CODE

Program POJ1325;//By_ThispoetConst	maxn=100;Var	i,j,m,n,p,q,k,ans					:Longint;	pre,other,last						:Array[0..maxn*10]of Longint;	res									:Array[0..maxn]of Longint;	state								:Array[0..maxn]of Boolean;Function Dfs(i:Longint):Boolean;var j,k:Longint;begin	j:=last[i];	while j<>0 do		begin			k:=other[j];			if not state[k] then				begin					state[k]:=true;					if (res[k]=0)or(Dfs(res[k]))then						begin							res[k]:=i;							exit(true);						end;				end;			j:=pre[j];		end;	exit(false);end;BEGIN	readln(n,m,k);	while n<>0 do 		begin					fillchar(last,sizeof(last),0);			for i:=1 to k do				begin					readln(j,p,q);					if p*q=0 then continue;					pre[i]:=last[p];last[p]:=i;other[i]:=q;				end;			ans:=0;			fillchar(res,sizeof(res),0);			for i:=1 to n do				begin					fillchar(state,sizeof(state),0);					if Dfs(i) then inc(ans);				end;						writeln(ans);						read(n);			if n<>0 then readln(m,k);					end;END.