Link Sub: http://www.spoj.com/PTIT/problems/PTIT121G/
Người Gửi: Dương Lee
- Problem:
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.
- 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
Example:
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.
- ‘YES’ nếu có thể chia.
- ‘NO’ nếu không thể chia.
Input
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
Output:
YES
- Solution:
- Với bài này chỉ có 2 nhóm và N nhỏ nên ta có thể giải quyết như sau:
Với mỗi một người ta kiểm tra xem có quen biết với bất kì người nào nào trong 2 nhóm N1 và N2 không?
+ Nếu có quen biết người trong N1 và không quen người nào trong N2 ta cho người đó vào N2;
+ Nếu có quen biết người trong N2 và không quen người nào trong N1 ta cho người đó vào N1;
+ Nếu có quen biết người trong N1 và có quen biết người trong N2 ta không thể làm thỏa mãn yêu cầu.
+ Nếu có không quen người nào trong N1 và không quen người nào trong N2 ta cho người đó vào N1.
Lưu Ý: N==1 vẫn thỏa mãn YES @@
Với mỗi một người ta kiểm tra xem có quen biết với bất kì người nào nào trong 2 nhóm N1 và N2 không?
+ Nếu có quen biết người trong N1 và không quen người nào trong N2 ta cho người đó vào N2;
+ Nếu có quen biết người trong N2 và không quen người nào trong N1 ta cho người đó vào N1;
+ Nếu có quen biết người trong N1 và có quen biết người trong N2 ta không thể làm thỏa mãn yêu cầu.
+ Nếu có không quen người nào trong N1 và không quen người nào trong N2 ta cho người đó vào N1.
Lưu Ý: N==1 vẫn thỏa mãn YES @@
- Code:
C++:
https://ideone.com/O7gxFy
#include <iostream>
#include <vector>
using namespace std;
int N;
int A[102][102];
int read ()
{
cin>>N;
if (N==0) return 0;
for (int i=1; i<=N; i++)
{
for (int j=1; j<=N; j++)
{
cin>>A[i][j];
}
}
return 1;
}
int phanNhom()
{
vector <int> N1;
vector <int> N2;
for (int i=1; i<=N; i++)
{
int kt1=0;
for (int j=0; j<N1.size(); j++)
{
if (A[i][N1[j]]==1)
{
kt1 = 1;
break;
}
}
int kt2=0;
for (int j=0; j<N2.size(); j++)
{
if (A[i][N2[j]]==1)
{
kt2 = 1;
break;
}
}
if (kt1==1 && kt2==0)
N2.push_back(i);
else if (kt1==0 && kt2==1)
N1.push_back(i);
else if (kt1==1 && kt2==1)
return 0;
else
N1.push_back(i);
}
return 1;
}
int main ()
{
while (read())
{
if (phanNhom()==1)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
} JAVA:
...Python:
...