jiry_2's Blog

开始以为是裸的匈牙利算法，然后就WA了。后来想过用费用流或者KM通过用加权来解决但是都无果而终。后来突然发现如果要一关关闯下去一旦有一关找不到匹配那么就闯关失败了，应该就要BREAK掉了，这样一搞果然就AC了。

program p1191;
	type
		bian=record
			next,point:longint;
		end;
	var
		aimy,p:array[1..3000] of longint;
		v:array[1..2000] of boolean;
		b:array[1..10000] of bian;
		tot,len,n,m,i,j,k1,k2:longint;
	procedure add(k1,k2:longint);
		begin
			inc(len);
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	function find(k:longint):boolean;
		var
			i,j:longint;
		begin
			if k=0 then exit(true);
			i:=p[k];
			while i<>0 do begin
				j:=b[i].point;
				if v[j]=false then begin	
					v[j]:=true;
					if find(aimy[j])=true then begin
						aimy[j]:=k;
						exit(true);
					end;
				end;
				i:=b[i].next;
			end;
			exit(false);
		end;
	begin
		readln(m,n);
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		fillchar(aimy,sizeof(aimy),0);
		len:=0;
		for i:=1 to n do begin
			readln(k1,k2);
			add(i+m,k1+1);
			add(i+m,k2+1);
		end;
		tot:=0;
		for i:=m+1 to m+n do begin
			fillchar(v,sizeof(v),false);
			if find(i) then inc(tot) else break;
		end;
		writeln(tot);
	end.