Nội dung Bài tập
- Mã:
- [DHLTNC]_Nhom02_BT3
- Tên:
- Ghép Cừu
- Dạng thi:
- oi
- Thang điểm:
- 20 điểm
- Giới hạn thời gian:
- 1 giây
- Giới hạn bộ nhớ:
- 256 MB
- Được tạo bởi:
- 4301103014
Bài toán ghép cặp: có m con cừu và n cái lồng kích thước to nhỏ khác nhau. Con
cừu nhỏ có thể nhốt trong cái lồng to nhưng con cừu to thì không thể ở trong cái
lồng nhỏ. Hãy tìm cách ghép cừu và lồng sao cho số cặp được ghép là nhiều nhất.
Input
Dòng đầu tiên chứa 4 số nguyên dương n, m, s, t, (2 ≤ n ≤ 50) tương ứng là số
đỉnh, số cạnh của đồ thị, chỉ số của đỉnh phát và đỉnh thu.
m dòng tiếp theo, mỗi dòng có 2 số u, v cách nhau ít nhất một dấu cách thể hiện có
cung u, v trong mạng.
Output
In ra một số duy nhất là giá trị số cặp lớn nhất trên mạng.
Ví dụ:
input
10 16 0 9
0 1
0 2
0 3
0 4
1 6
2 5
2 7
2 8
3 6
4 6
4 7
4 8
5 9
6 9
7 9
8 9
output:
3
Theme :
Mời bạn soạn code
Ai có thể xem bài này :
Thông tin
Phần thảo luận
#include <bits/stdc++.h>using namespace std;//Tự cho là gồm 4 chữ số , vì đề bài k n...