-
09-04-2011, 04:59 PM #1Junior Member
- Ngày tham gia
- Sep 2015
- Bài viết
- 0
Bài toán cực tiểu tổng, cực tiểu trị lớn nhất trên đồ thị
1. Trình bày bài toán cực tiểu tổng, cực tiểu trị lớn nhất trên đồ thị.
2. Trình bày thuật toán tìm cực tiểu tổng, cực tiểu trị lớn nhất trên đồ thị.
3. Thiết kế cấu trúc dữ liệu và giải thuật tìm cực tiểu tổng, cực tiểu trị lớn nhất.
4. Viết chương trình cài đặt thuật toán tìm cực tiểu tổng, cực tiểu trị lớn nhất bằng ngôn ngữ C.
File dữ liệu đầu vào: GRAPH.INP có cấu trúc
n m (số đỉnh, số cạnh)
a1 b1 c1 (đỉnh đầu, đỉnh cuối, trọng số)
a2 b2 c2
....
am bm cm
File dữ liệu đầu ra: MINSUMA.OUT có cấu trúc
S (tổng cực tiểu)
v1 v2 ... vk (các đỉnh cực tiểu tổng)
M (cực tiểu trị lớn nhất)
v1 v2 ... vm (các đỉnh cực tiểu trị lớn nhất)
Ví dụ:
GRAPH.INP
7 6
1 2 1
2 3 1
3 4 1
4 5 1
4 6 2
4 7 2
MINSUMA.OUT
11
3
3
3 4
----------------------------------------------------------------------------------------
Đây là 1 ứng dụng của thuật toán Floyd tìm đường đi ngắn nhất với mọi cặp đỉnh trên đồ thị. Ở đây tôi không hiểu "cực tiểu tổng, cực tiểu trị lớn nhất trên đồ thị" là gì cả. Đã tìm đọc nhiều tài liệu nhưng không thấy nói đến vấn đề này.
Xin mọi người giải đáp giúp.View more random threads:
- [ Solved ]Tham chiếu hàm ! Sự khác biệt là j ?
- Giúp em sưa đoạn code này đi ạ!!
- [ Solved ]Nhập xuất file sử dụng fstream
- vấn đề truyền tham chiếu, cấp phát bộ nhớ động trong C++
- quản lí học sinh của một trường cấp 3
- thắc mắc về thao tác trong con trỏ với tệp
- Sắp xếp thự tự trong mảng
- Cần Giúp Đỡ Lỗi Bài Tập Danh Sách Liên Kết Đơn
- Help mình về việc in ra subset của 1 set
- Thuật toán quay lui phân tích số nguyên dương N thành tổng các số nguyên dương .
Rocket 1h là thực phẩm chức năng giúp tăng cường sinh lý nam có nguồn gốc hoàn toàn từ dược liệu tự nhiên. Rất nhiều nam giới đã tuyển lựa Rocket 1h như một phương thuốc hữu hiệu để cải thiện tình...
Nguyên nhân của cặp đôi nam nữ mua...