01/10/2018, 08:54
[Hỏi] Toán rời rạc
Kì này em có học môn này, em có đáng ký bài tập lớn, nhưng chưa có kinh nghiệm làm bài tập lớn, các anh chị có thể chia sẻ kinh nghiẹm giúp em được không ạ. Em đọc đề tài thì chưa hiểu lắm, em mong được mọi người giải thích cho em hiểu ạ, em cám ơn . đây là link đề tài http://poj.org/problem?id=3275
Bài liên quan
Cho N con bò, đánh thứ tự từ 1->N
Cho M cặp bò được so sánh số lượng sản xuất sữa giữa 2 con bò.
Xác định xem cần tối thiểu bao nhiêu cặp bò nữa để người nông dân có thể sắp xếp sản lượng sữa bò sản xuất từ cao đếm thấp.
Dòng đầu là 2 số N và M
N là số bò trong nông trại, M là số cặp bò đã được so sánh
M dòng tiếp theo là số thứ tự 2 con bò X và Y. Tức chỉ rằng con bò X sản xuất nhiều sữa hơn Y.
Vd:
4 3
1 2
1 3
2 4
Tứcđề nói có 4 con bò và 3 cặp so sánh,
Cặp đầu biết được con bò 1 cho nhiều sữa hơn con bò 2
Cặp 2 biết được con bò 1 cho nh sữa hơn bò 3
Cặp 3 biết được bò 2 cho nh sữa hơn bò 4
Từ đó biết được 1 > 2; 1 > 3; 2 > 4
-> 1 > 2 > 4 và 1 > 3
Bây giờ người nông dân ko biết 4 > 3 hay 3 > 4 -> cần so sánh thêm 1 cặp nữa sẽ biết được số sữa bò cho theo thứ tự giảm dần.
Vậy output của ví dụ trên là 1.
Có lẽ đây là 1 bài về đồ thị.
Giải thuật sắp xếp topo thôi bạn. Input là một đồ thị có hướng không có vòng lặp. Ouput là thứ tự topo các node của đồ thị.
vâng em cám ơn anh. Em học môn cấu trúc dữ liệu và giải thuật thì thầy giáo bỏ phần đồ thị, nên em đọc không hiểu gì cả.
em đọc bài dịch của anh em hiểu vấn đề của em rồi. em cám ơn anh ạ