PTIT121G spoj PTIT – Quan hệ
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT121G/ 1. Đề bài PTIT121G spoj Có N người mang tên tương ứng là 1, 2, …, N và tình trạng quen biết của N người này được cho bởi mảng đối xứng A[1..N][1..N] trong đó A[i][j] = A[j][i] = 1 nếu i quen j và bằng 0 nếu i không ...
Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT121G/
1. Đề bài PTIT121G spoj
Có N người mang tên tương ứng là 1, 2, …, N và tình trạng quen biết của N người này được cho bởi mảng đối xứng A[1..N][1..N] trong đó A[i][j] = A[j][i] = 1 nếu i quen j và bằng 0 nếu i không quen j (quy ước A[i,i]=0). Hãy xét xem liệu có thể chia N người đó thành 2 nhóm mà trong mỗi nhóm hai người bất kì đều không quen nhau?
Input
Gồm nhiều bộ test, mỗi bộ test có dạng như sau:
– Dòng thứ nhất: Ghi số nguyên dương 1<=N <= 100
– N dòng tiếp theo, dòng thứ i ghi N số A[i][1], …, A[i][N].
Bộ test kết thúc bởi dòng chứa số N=0.
Output
Với mỗi bộ test, in ra trên một dòng:
– ‘YES’ nếu có thể chia.
– ‘NO’ nếu không thể chia.
Example
| INPUT | OUTPUT |
| 11 0 1 0 0 1 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 | YES |
2. Hướng dẫn PTIT121G spoj PTIT – Quan hệ
Xây dựng mảng DD[1..N] như sau:
- Khởi tạo mọi giá trị bằng 0.
- Bắt đầu chia nhóm từ người thứ nhất cho tới người thứ N. Khi xét người thứ i, những khả năng sau có thể xảy ra:
+ Nếu DD[i] = 0 (chưa được xếp nhóm) thì xếp vào nhóm 1(DD[i] = 1) và xếp những người j quen i vào nhóm 2 (cho DD[j] =2).
+ Nếu DD[i] = 1 và trong số những người quen i có một người j mà DD[j] cũng bằng 1 thì kết luận không xếp được.
+Nếu DD[i] = 2 và trong số những người quen i có một người j mà DD[j] cũng bằng 2 thì kết luận không xếp được.
3. Code tham khảo PTIT121G spoj PTIT – Quan hệ
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 | const fi='; fo='; nmax=100+1; type data=longint; var f,f1:text; n:data; A:array[1..nmax,1..nmax] of byte; DD:array[1..nmax] of byte; procedure xuli; var i,j,k,tmp:data; begin fillchar(dd,sizeof(dd),0); for i:=1 to n-1 do for j:=i+1 to n do if a[i,j]=1 then begin if (dd[i]=0) and (dd[j]=0) then begin dd[i]:=1; dd[j]:=2; continue; end; if dd[i]<>0 then begin if dd[i]=1 then tmp:=2 else tmp:=1; if dd[j]=0 then begin dd[j]:=tmp; end else if dd[j]=dd[i] then begin writeln(f,'NO'); exit; end; end else begin if dd[j]=1 then tmp:=2 else tmp:=1; dd[i]:=tmp end; end; writeln(f,'YES'); end; procedure docfile; var i,j,tmp:data; begin assign(f1,fi); reset(f1); assign(f,fo); rewrite(f); readln(f1,tmp); repeat if tmp=0 then break; n:=tmp; for i:=1 to n do begin for j:=1 to n do read(f1,a[i,j]); readln(f1); end; xuli; readln(f1,tmp); until tmp=0; close(f1); close(f); end; begin docfile; end. |
