Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

NKPOS - Người đưa thư

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/nkpos


Một bưu tá ở vùng quê cần chuyển thư cho người dân ở các ngôi làng cũng như ở trên các con đường nối giữa các ngôi làng. Bạn cần giúp bưu tá tìm hành trình đi qua mỗi ngôi làng và mỗi con đường ít nhất một lần (dữ liệu vào đảm bảo một hành trình như vậy tồn tại). Tuy nhiên, mỗi hành trình còn được gắn với một chi phí. Người dân ở các ngôi làng đều muốn bưu tá đến làng mình càng sớm càng tốt. Vì vậy mỗi ngôi làng đã thỏa thuận với bưu điện, nếu làng i là làng thứ k phân biệt được thăm trên hành trình và k ≤ wi, làng i sẽ trả wi – k euros cho bưu điện. Nếu k > wi , bưu điện đồng ý trả k - wi euros cho ngôi làng. Ngoài ra, bưu điện còn trả bưu tá một euro khi đi qua mỗi con đường trên hành trình.

Có n ngôi làng, được đánh số từ 1 đến n. Bưu điện được đặt ở ngôi làng số một, do đó hành trình cần bắt đầu và kết thúc tại ngôi làng này. Mỗi ngôi làng được đặt ở giao điểm của hai, bốn, hoặc tám con đường. Có thể có nhiều đường nối giữa hai ngôi làng. Con đường có thể là một vòng nối một ngôi làng với chính nó.

Yêu cầu: Viết chương trình xác định một hành trình đi qua mỗi ngôi làng và mỗi con đường ít nhất một lần, sao cho tổng lợi nhuận của bưu điện là lớn nhất (hay tổng thiệt hại là bé nhất).

Dữ liệu

  • Dòng đầu tiên chứa 2 số nguyên n, m, cách nhau bởi khoảng trắng; n (1 ≤ n ≤ 200), là số ngôi làng và m là số con đường.
  • Mỗi dòng trong số n dòng sau chứa một số nguyên dương. Dòng thứ i+1 chứa số wi, 0 ≤ wi ≤ 1000, xác định chi phí được trả bởi làng i.
  • Mỗi dòng trong số m dòng sau chứa hai số nguyên dương cách nhau bởi khoảng trắng, mô tả một con đường nối hai ngôi làng.

Kết qủa

  • Dòng đầu tiên chứa số nguyên dương k, độ dài của hành trình.
  • Dòng thứ hai theo chứa k+1 số cho biết các ngôi làng được thăm theo thứ tự trên hành trình, cách nhau bởi khoảng trắng, trong đó v1=vk+1=1.

Ví dụ

Dữ liệu:
6 7
1
7
4
10
20
5
2 4
1 5
2 1
4 5
3 6
1 6
1 3

Kết qủa
7
1 5 4 2 1 6 3 1

Được gửi lên bởi:Jimmy
Ngày:2008-01-04
Thời gian chạy:0.100s-1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED
Nguồn bài:Baltic OI 2001

hide comments
2014-12-08 16:22:00 NTT
bài này die rồi ???
2014-06-26 09:43:40 Lãng Tử Lang Thang
Bài này chỉ lừa hs, Làm tí euler là ra ngay ý mà! :))
2014-06-26 09:42:28 ๖ۣۜPublic °°
bài này lằng nhằng quá, lừa tình học sinh
2013-12-18 15:54:09 Xiao Lang
Những bài kiểu này không cần quan tâm đến trọng số. Đi kiểu gì kết quả vẫn là thế thôi. Vấn đề là tìm chu trình ơ le bằng stack là AC
2013-12-12 16:30:32 Nguyễn Hoàng Nam
vi phai di qua tat ca cac canh nen so tien thuong khong doi =1+..n=> cho vao de danh lua
2013-12-12 16:24:23 Nguyễn Hoàng Nam
chu trinh euler
2013-12-04 06:50:36 ==:xi ni chi CU ÐÔ:==
bạn trường làm cách nào thía??
2013-12-04 05:51:39 Human Immunodeficiency Virus
1 ĐẤM AC =))))
2013-11-23 09:55:24 Khắc Bảo
Bài này sao mình làm quài cũng có 10 điểm vậy. Ai giúp mình với
2013-09-04 14:56:13 a;slkfjasl;fkj
ko ảo lắm đâu :*

Last edit: 2013-09-04 15:15:46
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.