English

Vietnamese

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/fz10b

Tóm tắt đề:

Cho một mạng có N đỉnh, M cạnh vô hướng và một đỉnh phát S. Mỗi cạnh (X, Y) của mạng có khả năng thông qua là K. Hãy tìm cách chọn 1 đỉnh thu T khác với S sao cho luồng cực đại trên mạng với đỉnh phát S và đỉnh thu T có giá trị nhỏ nhất.

Input
Có nhiều bộ test, dữ liệu kết thúc bằng  "0 0 0"
Với mỗi test:
Dòng đầu chứa 3 số nguyên N, M và S, thể hiện số đỉnh, số cạnh, và chỉ số đỉnh phát (các đỉnh đánh số từ 1 đến N).
M dòng tiếp theo mô tả các cạnh của đồ thị. Mỗi dòng chứa 3 số nguyên X, Y và K, thể hiện một cạnh nối 2 đỉnh X và Y với khả năng thông qua là  K.
Giới hạn:
1 < N ≤ 300, 0 < M ≤ 50000, 0 < S, X, Y ≤ N, 0 < K ≤ 1000000
 
Output
Với mỗi test, in ra 1 số nguyên W duy nhất thể hiện luồng cực đại nhỏ nhất tìm được trong số các cách chọn đỉnh thu.

Sample Input
5 5 1 
1 2 5 
2 4 6 
1 3 7 
3 4 3 
5 1 10 
0 0 0

 
Sample Output
8