MATCH1 spoj – Cặp ghép không trọng số
Nguồn đề bài cặp ghép không trọng số: http://vn.spoj.com/problems/MATCH1/ 1. Đề bài cặp ghép không trọng số Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, …, xm, các đỉnh của Y ký hiệu là y1, y2, …, yn. Một bộ ghép trên G là một tập các cạnh ...
Nguồn đề bài cặp ghép không trọng số: http://vn.spoj.com/problems/MATCH1/
1. Đề bài cặp ghép không trọng số
Cho đồ thị hai phía G = (X U Y, E); Các đỉnh của X ký hiệu là x1, x2, …, xm, các đỉnh của Y ký hiệu là y1, y2, …, yn.
Một bộ ghép trên G là một tập các cạnh thuộc E đôi một không có đỉnh chung.
Yêu cầu: Hãy tìm bộ ghép cực đại (có nhiều cạnh nhất) trên G.
Chú ý : Dùng Eof chứ không dùng SeekEof.
Input
• Dòng 1: Chứa hai số m, n (1 ≤ m, n ≤ 100)
• Các dòng tiếp, mỗi dòng chứa hai số nguyên dương i, j cho biết thông tin về một cạnh (xi, yj) thuộc E.
Output
• Dòng 1: Ghi số cạnh trong bộ ghép cực đại tìm được (K).
• K dòng tiếp theo, mỗi dòng ghi thông tin về một cạnh được chọn vào bộ ghép cực đại: Gồm 2 số u, v thể hiện cho cạnh nối (xu, yv).
Example
Input:
4 5
1 1
1 4
2 1
2 2
2 4
3 2
3 3
4 2
4 3
Output:
4
1 1
2 4
3 3
4 2
2. Code cặp ghép không trọng số Pascal
Đây là code thuật toán cặp ghép thôi. không có hướng dẫn gì cả.
Code mẫu cặp ghép được viết dựa trên Cuốn DSAP của thầy Lê Minh Hoàng, giáo viên khối chuyên Sư Phạm.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 | const fi='; nmax=1000; type data=longint; var f:text; A:array[0..nmax+1,0..nmax+1] of byte; Q,MatchX,MatchY,tr:array[0..nmax+1] of data; n,m,dau,cuoi:data; procedure docfile; var i,j,u,v:data; begin assign(f,fi); reset(f); fillchar(a,sizeof(a),0); readln(f,m,n); while not eof(f) do begin readln(f,u,v); a[u,v]:=1; end; close(f); end; procedure them(x:data); begin inc(cuoi); q[cuoi]:=x; end; function lay:data; begin lay:=q[dau]; inc(dau); end; function BFS:data; var i,j,u,v:data; begin dau:=1; cuoi:=0; fillchar(tr,sizeof(tr),0); for i:=1 to m do if matchX[i]=0 then them(i); while dau<=cuoi do begin u:=lay; for v:=1 to n do if (a[u,v]=1) and (tr[v]=0) then begin tr[v]:=u; if matchy[v]=0 then exit(v); them(matchy[v]); end; end; exit(0); end; procedure enlager(u:data); var v,next:data; begin repeat v:=tr[u]; next:=matchx[v]; matchx[v]:=u; matchy[u]:=v; u:=next; until u=0; end; procedure xuli; var i,j,res,d:data; begin fillchar(matchx,sizeof(matchx),0); fillchar(matchy,sizeof(matchy),0); repeat d:=bfs; if d<>0 then enlager(d); until d=0; res:=0; for i:=1 to m do if matchx[i] <>0 then inc(res); writeln(res); for i:=1 to m do if matchx[i]<>0 then writeln(i,' ',matchx[i]); end; begin docfile; xuli; end. |
