Người đưa thư

Điểm: 0,26 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 512M

Input: stdin

Output: stdout

Nguồn bài:

Baltic OI 2001

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

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 \leq w_{i}$ , làng $i$ sẽ trả $w_{i} - k$ euros cho bưu điện. Nếu $k > w_{i}$ , bưu điện đồng ý trả $k - w_{i}$ 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).

Input

Dòng đầu tiên chứa 2 số nguyên $n$ , $m$ , cách nhau bởi khoảng trắng; $n$ ( $1 \leq n \leq 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ố $w_{i}$ , $0 \leq w_{i} \leq 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.

Output

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 đó $v_{1}$ = $v_{k + 1}$ = 1.

Sample Input

Copy

Sample Output

Copy

7
1 6 3 1 5 4 2 1

Bình luận

Hãy đọc nội quy trước khi bình luận.

-9

avatarstar1133 đã bình luận 2:34:43 sa, 15/07/2022

trùm trường là t

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-9

chubedanye đã bình luận 9:14:25 sa, 16/03/2023

còn tao là siêu nhân điện quang siêu mạnh siêu phấn đông siêu cấp phấn đông siêu siêu siêu siêu siêu siêu siêu siêu siêu ssieeu siuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuu

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-11

Moderize đã bình luận 2:35:40 sa, 18/02/2022

include <bits/stdc++.h>

using namespace std;

// DEFINE - (1)

define ll long long;

define ull unsigned long long;

define db double;

define ldb long double;

define FOR(i, l, r) for (int (i) = (l); (i) <= (r); ++(i))

define FOS(i, r, l) for (int (i) = (r); (i) >= (l); --(i))

define EACH(i, x) for (auto &(i) : (x))

define all(x) (x).begin(), (x).end()

define sz(x) (int)(x).size()

define lcm(a, b) (a) / gcd((a), (b)) * (b)

define gcd __gcd

define WHILE while

define pb popback

define pf popfront

define lb lower_bound

define ub upper_bound

define mtp make_tuple

define st first

define nd second

define pi pair<int, int>

define pll pair<ll, ll>

define vi vector<int>

define vll vector<ll>

define vpi vector<pi>

define vpll vector<pll>

define pb push_back

define lb lower_bound

define ub upper_bound

define oo (int)2e9 + 1

// MAGIC - (2) void thanchu(){ //freopen(".INP","r",stdin); //freopen(".OUT","w",stdout); iosbase::syncwithstdio(0); cin.tie(NULL); cout.tie(NULL); }

// DECLARATION - (3) int n, m; vector<int> g[201];

void euler(){ cout << m << endl; stack<int> st, res; st.push(1); while(!st.empty()){ int u = st.top(); if (!g[u].empty()){ int v = g[u][0]; st.push(v); g[u].erase(g[u].begin()); g[v].erase(find(g[v].begin(), g[v].end(), u)); } else{ st.pop(); res.push(u); } } while(!res.empty()){ cout << res.top() << " "; res.pop(); } }

signed main(){ thanchu(); cin >> n >> m; for(int i = 0; i < n; i++){ int w; cin >> w; } for(int i = 0; i < m; i++){ int u, v; cin >> u >> v; g[u].pushback(v); g[v].push_back(u); } euler(); return 0; }

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.