magirl
18-01-2003, 16:54
Chắc bài này đối với các bác thì rất dễ nhưng em chẳng thấy dễ chút nào, các cao thủ giúp em nhé:
một toà soạn báo cần phân công n phóng viên , mỗi phóng viên đến một trong số n địa điểm khác nhau để săn lùng tin về giải vô địch bóng đá. Mỗi phóng viên được quyền đề xuất một danh sách gồm 3 địa điểm mà họ muốn đến xếp theo thứ tự nhất, nhì, ba. Một cách phân công được gọi là chấp nhận được là tất cả các phong viên được đến ít nhất một địa điểm trong danh sách 3 địa điểm mong ước. Nếu có cách phân công chấp nhận được, toà soạn lại quan tâm đến cách phân công trong đó số phóng viên được đến địa điểm họ ưa thích nhất là lớn nhất. Cách phân công như vậy gọi là cách phân công phù hợp.
Yêu cầu: nếu có cách phân công chấp nhận được, cần tìm cách phân công phù hợp trong đó số phóng viên được đến địa điểm mà họ ưa thích nhì là lớn nhất, ngược lại cần đưa ra cách phân công mà trong đó số phóng viên không được đến địa điểm nào trong danh sách 3 địa điểm ưa thích của họ là nhỏ nhất
Dữ liệu
- n
- n dòng tiếp theo, dòng thứ i chứa 3 số nguyên dương ai,bi,ci là danh sách 3 địa điểm ưa thích của phóng viên i (theo thứ tự nhất, nhì, ba)
output
- số pv không được đáp ứng nguyện vong;số phóng viên được cử đến địa điểm ưa thích nhất, nhì
- dòng thứ i trong số n dòng tiếp theo ghi địa điểm mà phóng viên i được cử đến phân công
* thực ra bài này sách đã giải rồi nhưng em nghĩ là nó giải sai, các bác giúp đỡ em nhé
một toà soạn báo cần phân công n phóng viên , mỗi phóng viên đến một trong số n địa điểm khác nhau để săn lùng tin về giải vô địch bóng đá. Mỗi phóng viên được quyền đề xuất một danh sách gồm 3 địa điểm mà họ muốn đến xếp theo thứ tự nhất, nhì, ba. Một cách phân công được gọi là chấp nhận được là tất cả các phong viên được đến ít nhất một địa điểm trong danh sách 3 địa điểm mong ước. Nếu có cách phân công chấp nhận được, toà soạn lại quan tâm đến cách phân công trong đó số phóng viên được đến địa điểm họ ưa thích nhất là lớn nhất. Cách phân công như vậy gọi là cách phân công phù hợp.
Yêu cầu: nếu có cách phân công chấp nhận được, cần tìm cách phân công phù hợp trong đó số phóng viên được đến địa điểm mà họ ưa thích nhì là lớn nhất, ngược lại cần đưa ra cách phân công mà trong đó số phóng viên không được đến địa điểm nào trong danh sách 3 địa điểm ưa thích của họ là nhỏ nhất
Dữ liệu
- n
- n dòng tiếp theo, dòng thứ i chứa 3 số nguyên dương ai,bi,ci là danh sách 3 địa điểm ưa thích của phóng viên i (theo thứ tự nhất, nhì, ba)
output
- số pv không được đáp ứng nguyện vong;số phóng viên được cử đến địa điểm ưa thích nhất, nhì
- dòng thứ i trong số n dòng tiếp theo ghi địa điểm mà phóng viên i được cử đến phân công
* thực ra bài này sách đã giải rồi nhưng em nghĩ là nó giải sai, các bác giúp đỡ em nhé