trang chủ / đề bài / icpc21_mb_m

Đồ thị

Đề bài

Mô tả

Cho một đồ thị gồm n đỉnh và m cung có hướng. Các đỉnh được đánh số từ 1 đến n, các cung được đánh số từ 1 đến m. Cung thứ i đi từ đỉnh si đến đỉnh ti và có chi phí ci.

Trong bài này, một đường đi hợp lệ là một dãy các cung trong đó cung đầu tiên xuất phát từ đỉnh 1, cung cuối cùng kết thúc tại đỉnh n, và mỗi cung kết thúc tại đỉnh xuất phát của cung tiếp theo. Chính xác hơn, một đường đi hợp lệ được biểu diễn bởi dãy chỉ số (e1,e2,…,ek) thỏa mãn tất cả các điều kiện sau:

  • 1≤e1,e2,…,ek≤m;
  • se1=1;
  • tek=n;
  • tej=sej+1 với mọi j thỏa mãn 0<j<k.

Lưu ý rằng các chỉ số này không nhất thiết phân biệt, nghĩa là một đường đi hợp lệ có thể đi qua một cung nhiều lần.

Nhiệm vụ của bạn là đánh dấu một số cung (có thể không cung nào hoặc tất cả các cung) là đặc biệt sao cho yêu cầu sau được thỏa mãn: mọi đường đi hợp lệ của đồ thị đều đi qua cung đặc biệt đúng một lần. Nói cách khác, nếu dãy chỉ số (f1,f2,…,fk) biểu diễn một đường đi hợp lệ thì có đúng một chỉ số l (1≤l≤k) mà cung thứ fl được đánh dấu đặc biệt. Ngoài ra, tổng chi phí của các cung đặc biệt phải nhỏ nhất có thể.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test có dạng như sau:

  • Dòng đầu tiên chứa hai số nguyên n và m (2≤n≤100, 1≤m≤2500): số đỉnh và số cung của đồ thị.
  • m dòng tiếp theo, mỗi dòng chứa ba số nguyên si, ti, ci (1≤si,ti≤n, 1≤ci≤109): đỉnh xuất phát, đỉnh kết thúc và chi phí của cung thứ i.
  • Dòng cuối cùng là một dòng trống.

Dữ liệu vào kết thúc bằng hai số 0 (không phải một bộ test). Dữ liệu đảm bảo:

  • Với mọi cung, đỉnh xuất phát khác đỉnh kết thúc.
  • Trong mỗi đồ thị, mỗi cặp có thứ tự (si,ti) xuất hiện nhiều nhất một lần.
  • Luôn tồn tại một đường đi hợp lệ.

Tổng các giá trị n của mọi bộ test không vượt quá 1000. Tổng các giá trị m của mọi bộ test không vượt quá 25000.

Dữ liệu ra

Với mỗi bộ test, in kết quả trên một dòng: nếu không thể đánh dấu các cung để thỏa mãn yêu cầu, in ra IMPOSSIBLE. Ngược lại, in ra tổng chi phí nhỏ nhất của các cung đặc biệt.

Ràng buộc

  • 2≤n≤100, 1≤m≤2500.
  • 1≤si,ti≤n, si≠ti, 1≤ci≤109; các cặp (si,ti) trong một đồ thị đôi một khác nhau.
  • Luôn tồn tại một đường đi hợp lệ.
  • Tổng n không vượt quá 1000, tổng m không vượt quá 25000.

Ví dụ

Input Output Giải thích
4 5
1 2 1
2 3 1
3 4 1
1 3 8
2 4 8

2 2
2 1 1
1 2 1

0 0
9
IMPOSSIBLE
Ở bộ test thứ nhất có ba đường đi hợp lệ, với dãy chỉ số cung là (4,3), (1,5) và (1,2,3). Cách tối ưu là đánh dấu cung thứ nhất và cung thứ tư. Đánh dấu cung thứ nhất và cung thứ ba là không hợp lệ vì đường đi (1,2,3) đi qua cung đặc biệt hai lần. Ở bộ test thứ hai, đường đi hợp lệ có thể lặp lại cung: (2,1,2) hay (2,1,2,1,2) đều hợp lệ. Vì cung thứ hai xuất hiện nhiều lần trong các đường đi này nên không thể đánh dấu nó, do đó không có cách đánh dấu nào.
3 3
1 2 5
2 1 2
2 3 4

3 3
1 2 3
2 3 1
3 2 1

0 0
4
3
Ví dụ bổ sung (không có trong đề gốc). Ở bộ test thứ nhất, đánh dấu cung 2→3: mọi đường đi hợp lệ có dạng 1→2→1→…→2→3 và đi qua cung này đúng một lần. Ở bộ test thứ hai, không thể đánh dấu cung 2→3 vì đường đi 1→2→3→2→3 đi qua nó hai lần; đánh dấu cung 1→2 với chi phí 3.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0