管道网络

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

思路

题目不好理解，画个图就好明白了

把上面的输入输出用例画出来就是水管的连接图，箭头连接的是不同的人家，箭头上面的数字是水管的直径，我们需要在没有输入水管的人家安装tank，在没有输出的人家安装tap，所以需要安装的是5 -> 6, 2 -> 8, 3 -> 1，至于安装在它们之间的最小水管大小，就是连通路径上的最小水管直径。比如5 -> 6连通路径上最小的直径是10，因此最后结果就是10。

解题思路：

1. 找到所有的起点（5， 2， 3）

   可以先记录所有路径的起点，和终点，最后用起点减去终点，就能找到所有真实的起点。

2. 从起点开始，找出下一条路径，直到没有下一条路径结束，记录结束的点（与上面对应的是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)