Đề bài: http://vn.spoj.com/problems/MATCH1/
Thuật toán:
- Đây là bài cơ bản cho thuật toán Cặp ghép
- Bạn có thể tham khảo tài liệu cực hay và dễ hiểu về thuật toán này tại: http://yeulaptrinh.pw/150/tong-hop-tai-lieu-ve-thuat-toan-cap-ghep/
Code:
const fi=''; fo=''; maxn=100; var a : array[1..maxn,1..maxn] of boolean; match : array[1..maxn] of longint; i,j,n,m,res : longint; procedure enter; var u,v : longint; begin assign(input,fi);reset(input); readln(n,m); while not eof(input) do begin readln(u,v); a[u,v] := true; end; end; procedure process; var found : boolean; nlist,i,j,old : longint; list : array[1..maxn] of longint; cx : array[1..maxn] of boolean; procedure dfs(u : longint); var i,v : longint; begin for v:=1 to m do if a[u,v] then if cx[v] then begin cx[v] := false; if match[v]=0 then found := true else dfs(match[v]); if found then begin match[v] := u; exit; end; end; end; begin nlist := n; for i:=1 to n do list[i ] := i; repeat old := nlist; fillchar(cx,sizeof(cx),true); for i:=nlist downto 1 do begin found := false; dfs(list[i]); if found then begin list[i] := list[nlist]; dec(nlist); end; end; until old = nlist; end; procedure print; begin assign(output,fo);rewrite(output); for i:=1 to m do if match[i]<>0 then inc(res); writeln(res); for i:=1 to m do if match[i]<>0 then writeln(match[i],' ',i); close(output); end; begin enter; process; print; end. |
BÌNH LUẬN MỚI