Description
Every house in the colony has at most one pipe going into it and at most one pipe going out of it. Tanks and taps are to be installed in a manner such that every house with one outgoing pipe but no incoming pipe gets a tank installed on its roof and every house with only an incoming pipe and no outgoing pipe gets a tap. Find the efficient way for the construction of the network of pipes.
Input
The first line contains an integer T denoting the number of test cases. For each test case, the first line contains two integer n & p denoting the number of houses and number of pipes respectively. Next, p lines contain 3 integer inputs a, b & d, d denoting the diameter of the pipe from the house a to house b.Constraints:1<=T<=50歪架，1<=n<=20存谎，1<=p<=50瞻凤，1<=a, b<=20骡送，1<=d<=100
Output
For each test case, the output is the number of pairs of tanks and taps installed i.e n followed by n lines that contain three integers: house number of tank, house number of tap and the minimum diameter of pipe between them.
Sample Input 1
1
9 6
7 4 98
5 9 72
4 6 10
2 8 22
9 7 17
3 1 66
Sample Output 1
3
2 8 22
3 1 66
5 6 10
思路
題目不好理解，畫個圖就好明白了
把上面的輸入輸出用例畫出來就是水管的連接圖待笑，箭頭連接的是不同的人家鸣皂，箭頭上面的數(shù)字是水管的直徑，我們需要在沒有輸入水管的人家安裝tank，在沒有輸出的人家安裝tap寞缝，所以需要安裝的是5 -> 6, 2 -> 8, 3 -> 1癌压，至于安裝在它們之間的最小水管大小，就是連通路徑上的最小水管直徑荆陆。比如5 -> 6連通路徑上最小的直徑是10滩届，因此最后結(jié)果就是10。
解題思路：
-
找到所有的起點（5被啼， 2帜消， 3）
可以先記錄所有路徑的起點，和終點浓体，最后用起點減去終點泡挺，就能找到所有真實的起點。
-
從起點開始命浴，找出下一條路徑娄猫，直到?jīng)]有下一條路徑結(jié)束，記錄結(jié)束的點（與上面對應(yīng)的是6咳促， 8稚新， 1）
記錄從起點到終點的路徑中勘伺，需要記錄管道直徑的最小值跪腹，最后輸出
python O(N)
def solve(p, pairs):
link, vals = {}, {}
for pair in pairs:
link[pair[0]] = pair[1]
vals[(pair[0], pair[1])] = pair[2]
starts = set(link.keys()) - set(link.values())
ans = []
for s in starts:
e = link[s]
val = vals[(s, e)]
while e in link:
val = min(val, vals[e, link[e]])
e = link[e]
ans.append((s, e, val))
return sorted(ans)
for _ in range(int(input())):
p, t = map(int, input().strip().split())
pairs = [tuple(map(int, input().strip().split())) for _ in range(t)]
res = solve(p, pairs)
print(len(res))
for ans in res:
print(*ans)
