Nubulsa Expo

View as PDF

Submit solution

Points: 1.86 (partial)
Time limit: 1.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
ACM ICPC Fuzhou 2010
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

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)~.(~1 < N \leq 300~, ~0 < M \leq 50000~, ~0 < S \leq 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~. (~0 < X~, ~Y \leq N~, ~0 < K \leq 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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.