FZ10B - Nubulsa Expo

no tags 

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 NM 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 XY 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 < SXY ≤ 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



Added by:Race with time
Date:2012-08-24
Time limit:0.101s-0.108s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM ICPC Fuzhou 2010