The German University in Cairo (GUC) dorm houses are numbered from 1 to n. Underground…
- User
The German University in Cairo (GUC) dorm houses are numbered from 1 to n. Underground water pipes connect these houses together. Each pipe has certain direction (water can flow only in this direction and not vice versa), and diameter (which characterizes the maximal amount of water it can handle).
For each house, there is at most one pipe going into it and at most one pipe going out of it. With the new semester starting, GUC student and dorm resident, Lulu, wants to install tanks and taps at the dorms. For every house with an outgoing water pipe and without an incoming water pipe, Lulu should install a water tank at that house. For every house with an incoming water pipe and without an outgoing water pipe, Lulu should install a water tap at that house. Each tank house will convey water to all houses that have a sequence of pipes from the tank to it. Accordingly, each tap house will receive water originating from some tank house.
In order to avoid pipes from bursting one week later (like what happened last semester), Lulu also has to consider the diameter of the pipes. The amount of water each tank conveys should not exceed the diameter of the pipes connecting a tank to its corresponding tap. Lulu wants to find the maximal amount of water that can be safely conveyed from each tank to its corresponding tap. Input
The first line contains two space-separated integers n and p (1 ≤ n ≤ 1000, 0 ≤ p ≤ n) — the number of houses and the number of pipes correspondingly.
Then p lines follow — the description of p pipes. The i-th line contains three integers ai bi di, indicating a pipe of diameter di going from house ai to house bi (1 ≤ ai, bi ≤ n, ai ≠ bi, 1 ≤ di ≤ 106).
It is guaranteed that for each house there is at most one pipe going into it and at most one pipe going out of it.
Output
Print integer t in the first line — the number of tank-tap pairs of houses.
For the next t lines, print 3 integers per line, separated by spaces: tanki, tapi, and diameteri, where tanki ≠ tapi (1 ≤ i ≤ t). Here tanki and tapi are indexes of tank and tap houses respectively, and diameteri is the maximum amount of water that can be conveyed. All the t lines should be ordered (increasingly) by tanki.
Examples
Input
3 2 1 2 10 2 3 20
Output
1 1 3 10
Input
3 3 1 2 20 2 3 10 3 1 5
Output
0
Input
4 2 1 2 60 3 4 50
Output
2 1 2 60 3 4 50
Assistant
We need to read problem: "The German University in Cairo (GUC) dorm houses ...". It's basically about directed graphs where each node has at most one outgoing edge and at most one incoming edge. This implies the graph consists of disjoint components each of which is a set of directed paths and directed cycles (since each node indegree/outdegree <=1, the graph is a collection of directed chains and cycles). However, there can be isolated nodes too. The problem asks: for each node that has out-degree 1 and in-degree 0, i.e., a start of a path, we need to install a tank. For each node that has in-degree 1 and out-degree 0, i.e., end of a path, we need a tap. For each tank (source) there is a corresponding tap (sink) which is the end of the path that starts at that tank. However, if there is a cycle, then nodes in the cycle have both indegree and outdegree 1 (since there are no sinks or sources) — in that case no tank or tap should be installed? The problem says: "For every house with an outgoing water pipe and without an incoming water pipe, Lulu should install a water tank at that house. For every house with an incoming water pipe and without an outgoing water pipe, Lulu should install a water tap at that house." If there is a directed cycle, each node has incoming and outgoing (both 1), so no tank or tap. So cycles produce no output. Also isolated nodes (no edges) also produce nothing.
Then we need to find the maximal amount of water that can be safely conveyed from each tank to its corresponding tap. Since the pipes have diameters, the water flow must be ≤ the minimum diameter along the path from tank to tap. So essentially, for each source-to-sink path (a directed simple path because indegree/outdegree ≤1), we need to output the starting node, the ending node, and the minimum diameter along that path. And we need to output these sorted by tank (start) index.
Constraints: n up to 1000, p up to n. So we can simply parse and simulate. Since each node has at most one outgoing edge, we can maintain arrays: to[i] = neighbor if outgoing, and diam[i] = diameter of that outgoing pipe. Similarly indegree count. Then for each node that has outdegree=1 and indegree=0, we start traversing along the chain: keep track of current node, and maintain min diameter so far. When we reach a node that has outdegree=0 (i.e., no outgoing), that's the sink; but also need to ensure that node has indegree=1 (it will because we arrived along a pipe). But there could be a situation where we start from a source and then encounter a node that has both outgoing and incoming (like a path leads to a cycle?) Actually because each node has at most one outgoing and at most one incoming, any chain from a source can only end at a sink (outdegree=0) or could potentially enter a cycle? Let's think: Suppose we start from a node with indegree=0 and outdegree=1. Follow outgoing edges. If we ever come to a node that we've visited before, then we have a cycle. But because indegree/outdegree <=1, once we enter a cycle, the node we come to must have indegree 1 (coming from the path) but it also already has an outgoing edge (to continue the cycle). However, does the condition "each node has at most one incoming" hold? If a node is part of a cycle, its indegree from within the cycle is 1; if a path enters it, that would be a second incoming edge? Actually, in a directed graph with each node indegree ≤1, it is impossible for a path to enter a cycle because the node on the cycle already has indegree 1 from its predecessor in the cycle. If a path from outside tries to connect to that node, then that node would have indegree 2 (one from cycle, one from path). So such configuration is forbidden. Similarly, a node cannot have two incoming edges. Therefore, in such graphs, any node can belong to at most one simple directed path/cycle. Actually the structure is a set of disjoint directed paths and directed cycles. There is no branching: no node can have two outgoing. So there cannot be a path that leads into a cycle because that would give the entry node indegree 2 (one from within the cycle and one from path). So indeed the graph components are either simple directed paths (from a source to a sink) or directed cycles, or isolated nodes, or possibly a path that ends in a sink, or a source that goes into a path that ends, etc. But no other combination. So for each source (indegree=0, outdegree=1), following the outgoing edges leads to a sink (outdegree=0). However, there could also be a node with outdegree=1 and indegree=0 that goes into a node that is part of a cycle? Not allowed. So we are safe.
But wait: The problem statement says "For each house, there is at most one pipe going into it and at most one pipe going out of it." So indeed each node indegree ≤1, outdegree ≤1. So the graph is a collection of vertex-disjoint directed paths and cycles. So paths have sources (indegree 0, outdegree 1) and sinks (outdegree 0, indegree 1). Some nodes may have indegree 1 and outdegree 1 (middle nodes). Some may have indegree 0, outdegree 0 (isolated). So we need to list each source-sink path along with the minimum diameter on that path. But what if a source has outdegree 1 and indegree 0, but the path ends at a node that has outdegree 1? That would not be a sink. However, if a path ends, it must be because there is no outgoing edge. So the final node must have outdegree 0. Since each node has at most one outgoing, if it has no outgoing, that's a sink. So for a path starting from source, we will continue until we find a node with no outgoing. But could we encounter a node with indegree 0? Not possible because we came from previous node, so it will have at least indegree 1. So we are fine.
Now, note: The example with n=3 and p=3 forming a cycle gave output 0. That matches cycles produce nothing.
Another nuance: Could there be a case where a node has outdegree 0 and indegree 0? That's isolated and not considered as either tank or tap.
Also, what about a node that has outdegree 1 and indegree 0? That's a tank. A node with indegree 1 and outdegree 0? That's a tap.
But the problem says: "For every house with an outgoing water pipe and without an incoming water pipe, Lulu should install a water tank at that house. For every house with an incoming water pipe and without an outgoing water pipe, Lulu should install a water tap at that house." So indeed only sources and sinks.
Now, the required output: number of pairs (tank, tap). Then each line: tank, tap, and the maximum amount of water that can be conveyed. That should be the minimum diameter along the unique path from tank to tap. That's because to convey a certain amount, it must be ≤ all diameters, so maximum safe amount = min of diameters.
We must sort output by tank increasing.
Edge cases: p=0 -> no pipes -> output 0 (t=0). Also if there are sources but no sinks? Actually each source must lead to a sink, but could there be a source that leads to a node that also has outgoing? No, we would follow until outdegree 0. But if there is a node with outdegree 1 and indegree 1, it's middle. So we always end at sink.
But wait: what about a path that ends in a node that has outdegree? That can't happen because if it has outgoing, we would continue. So yes, the end is a node with no outgoing.
Implementation: We'll create arrays out[n+1] = 0 initially, indeg[n+1] = 0. For each pipe a->b with diameter d, set out[a] = b, diam[a] = d (since at most one outgoing, we can store the target and the diameter for that outgoing edge). And increment indeg[b]. Also we could verify that we don't exceed constraints, but input guaranteed.
After reading, we will iterate over i from 1 to n. For each i that is a tank: indeg[i]==0 && out[i]!=0. (out[i]!=0 meaning there is outgoing pipe). Then we start a traversal: cur = i, minD = INF (or diam[i] to start). Actually we can set minD = diam[i] (the diameter of the first pipe). But careful: The path includes the edges. The water travels through pipes. The tank at house i does not have an incoming pipe but has outgoing pipe. So the water goes from i to out[i] through that pipe, then onward. So the min diameter among all pipes from i to tap must be considered. So we traverse: start with current node = i, current min = diam[i] (if we want). But we need to include that first pipe's diameter. However, if the tank is the start, but the water originates at the tank? Actually the tank is the source of water. The water flows through the outgoing pipe. So indeed, the pipe from tank to next house has a diameter, and that must be considered. So we set minD = diam[i] (diameter of pipe from i to out[i]). Then we move to next = out[i], and while out[next] != 0 (i.e., there is outgoing pipe), update minD = min(minD, diam[next]), move next = out[next]. When we exit loop because out[next]==0, that node is the tap (sink). But we need to ensure that node has indegree at least 1 (it does, from previous). But also the problem definition: tap house must have incoming pipe and no outgoing. So that node qualifies. So final sink = next.
But there is a nuance: what if the path consists of just one pipe? That is, i has outgoing to j, and j has no outgoing. Then we traverse: start i, minD = diam[i], next = j, out[j]==0, so stop. The sink is j. That's correct.
Now, what about a case where the tank's outgoing pipe leads to a node that is a sink (outdegree 0). Yes.
We should also consider if there is a node that has outdegree 1 but indegree 0 that leads to a node with indegree 0? That can't happen because if node j has indegree 0, then there is no incoming edge; but we are coming from i->j, so j must have indegree at least 1, contradiction. So no.
Now, what about a node that is a tank but also has indegree? No, tank definition excludes indegree.
Now, we need to output the pairs. We should also consider that some tanks may belong to the same path? Actually each tank is the start of a path, and each sink is the end of a path. Since paths are disjoint, each tank corresponds to one sink. So we get t = number of sources (tanks). But is it possible that a source leads to a sink that is also a source? No, sink has outdegree 0.
Thus we can simply collect for each tank.
But we must also consider that a node might be both a tank and a tap? That would require indegree=0 and outdegree=0? That can't be because tank needs outgoing and no incoming, tap needs incoming and no outgoing. So impossible.
Now, what about cycles? In cycles, no node has indegree 0 or outdegree 0, so we ignore them.
Now, we need to order output by tank increasing. So we can collect results in a list and sort by tank, or since we iterate from 1 to n, we can just process in increasing order and output as we go (since we iterate i=1..n, if we process each tank, we will get them in increasing order. However, we must be careful: if we modify the graph during traversal? Not necessary. But we must ensure we don't double-count nodes that are part of multiple paths? Since paths are disjoint, each node belongs to at most one path. However, if we process tanks in increasing order and traverse the path, it's okay. But if there is a path that has a tank later but also includes nodes that are also tanks? No, a node that is a tank cannot be part of another path because it has indegree 0, so it can only be start, not interior. So traversal from a tank will only go through nodes that have indegree 1 (except maybe the tank which has indegree 0) and outdegree 1 (except sink). So those interior nodes are not tanks. So if we later encounter those interior nodes in the loop, they would not satisfy indegree==0 && outdegree!=0, so they won't be processed as tanks. So we can just process all i and if indeg[i]==0 and out[i]!=0, then traverse.
But what about the possibility that a node could be both a tank and also be the sink of another path? No.
Thus algorithm is straightforward.
But wait: The problem says "Print integer t in the first line — the number of tank-tap pairs of houses." So we need to output t lines. And "All the t lines should be ordered (increasingly) by tanki." That's fine.
But we need to also consider that there might be a path that starts at a tank but ends at a node that is not a tap? Could there be a path that ends at a node that is part of a cycle? Not allowed as argued. So always ends at a node with outdegree 0. However, there is also possibility that a node with outdegree 0 might have indegree 0 (isolated) but that can't be reached from a tank. So all sinks we encounter will have indegree 1, because they are reached via an edge.
Now, test example 1: n=3 p=2: 1->2 diam10, 2->3 diam20. indeg[1]=0, out[1]=2, indeg[2]=1, out[2]=3, indeg[3]=1, out[3]=0. So tanks: 1 (indeg0 out!=0). Traversal: start=1, minD=10, next=2, out[2]!=0, minD=min(10,20)=10, next=3, out[3]==0, sink=3. Output: 1 3 10. So matches.
Example 2: cycle. indeg each =1 out each =1. So no indeg0 or out0, output 0.
Example 3: n=4 p=2: 1->2 diam60, 3->4 diam50. indeg[1]=0 out[1]=2; indeg[2]=1 out[2]=0; indeg[3]=0 out[3]=4; indeg[4]=1 out[4]=0. Tanks: 1 and 3. Both produce paths: 1->2 min60; 3->4 min50. Output sorted by tank: 1 then 3. Matches.
Now, edge cases: Could there be a tank whose path goes through a node that is also a tank? No, as argued.
What about a situation where a node has indegree 0 and outdegree 1 but the path leads to a node that also has indegree 0? That can't happen because the second node would have indegree at least 1 from the incoming pipe. So it would have indegree 1. So not a tank.
Thus algorithm is fine.
Now, consider the possibility of "diameter" up to 1e6, we can store as int.
Complexities: O(n).
Now, we need to implement.
But wait: There's a nuance in the problem statement: "Lulu wants to find the maximal amount of water that can be safely conveyed from each tank to its corresponding tap." And they ask to output "diameteri". That suggests we output the minimum diameter. So yes.
Now, double-check: The input guarantee: "For each house, there is at most one pipe going into it and at most one pipe going out of it." So we can trust.
Implementation details:
We'll have arrays: to[1001] = 0 (the node to which there's an outgoing pipe, 0 if none). diam[1001] = 0 (diameter for that pipe). indeg[1001] = 0.
Read n, p.
For i in 1..p: read a, b, d. set to[a]=b; diam[a]=d; indeg[b]++.
Then we will create an empty vector result of tuples (tank, tap, minD).
Loop for i=1..n:
if indeg[i]==0 and to[i]!=0: // tank
cur = i;
minD = diam[cur]; // because we need to include the diameter of the pipe from cur to to[cur] (we assume to[cur]!=0)
next = to[cur];
while to[next] != 0: // while next has outgoing pipe
minD = min(minD, diam[next]); next = to[next];// now next is sink
tap = next;
// But we might also need to consider that the last edge's diameter might not have been considered if we stopped when to[next]==0? Actually we have considered diameters of edges along the way: we started with diam[cur] from i->to[i]. In the while loop, we update minD using diam[next] at each step before moving to next. However, when we exit the while loop, we have visited all edges except the last edge? Let's simulate: Suppose path i -> a -> b -> c, where c has outdegree 0. We start cur=i, minD = diam[i] (i->a). Then next = a. While to[next] != 0: a has to[a]=b !=0, so enter loop: minD = min(minD, diam[a]) (which is diameter a->b). Then set next = to[a] = b. Loop condition: to[b] = c? Actually to[b] = c, but c has outdegree 0? to[b]=c is not zero, because there is an outgoing pipe from b to c; to[b] is c, which is a node number, not zero. to[c] is zero because c has no outgoing. So we check to[next] (to[b])? Actually after we update next to b, the loop condition checks to[next] != 0. to[b] = c !=0, so we enter loop again: minD = min(minD, diam[b]) (diameter of b->c). Then set next = to[b] = c. Now next=c, loop condition: to[c]==0 so exit. So we have considered all edges including the last edge (b->c). So it's correct.
But what if the path is just i->j with to[j]==0? Then we start cur=i, minD=diam[i], next=j. Since to[next]==0, the while loop is skipped. We have considered only edge i->j. That's correct.
So we have tank=i, tap=next, minD.
Append to results.
Now, output.
But careful: There's a potential corner case: Could there be a tank that leads to a sink that is also a tank? No.
Also, could there be a node that has indegree 0 and outdegree 1 but the path eventually leads to a node that has outdegree 1 but indegree 0? That would be a contradiction as explained. So not.
Now, confirm with the example: All good.
Now, we should consider the possibility of multiple components: already handled.
Now, what about nodes with indegree 0 and outdegree 0? Not considered.
Now, is there any scenario where we have a tank but the sink does not have indegree 1? For instance, if we have a node that is a sink (outdegree 0) but indegree 0 (isolated) - that can't be reached. So all sinks we encounter have indegree >=1, but could it have indegree >1? Not allowed because max indegree 1. So indegree must be 1. So it qualifies as a tap.
Now, one more nuance: The problem says "For every house with an outgoing water pipe and without an incoming water pipe, Lulu should install a water tank at that house." So tanks are exactly those. Similarly taps: with incoming and no outgoing. So the pairs we output should be exactly those tank-tap pairs where there's a path from tank to tap (the unique path). So we should output all such tank-tap pairs. But is there any tank that does not have a corresponding tap? In this graph structure, each tank leads to a unique sink because we follow outgoing edges until outdegree 0. But is it possible that the path never ends? That would imply a cycle. However, as argued, starting from a node with indegree 0, if we follow outgoing edges, we cannot enter a cycle because that would give a node in the cycle indegree 2 (one from cycle, one from path). So it's impossible. So we always reach a node with outdegree 0.
But wait: What about a node that is part of a cycle and also has indegree 0? That would mean the cycle has a node with indegree 0. But then that node would have indegree 0, outdegree 1 (to next in cycle). That would be a tank! And the rest of the cycle nodes have indegree 1, outdegree 1. So we would have a cycle where the first node is a tank. But then the tank's outgoing leads to the cycle, and eventually we go around and come back to the tank? But that would give the tank indegree from the cycle? Let's examine: Suppose we have nodes 1->2, 2->3, 3->1. This is a cycle. Node 1 has indegree from node 3, so indegree=1, not 0. So it can't be a tank. To have a cycle with a node indegree 0, we need a scenario where the cycle is not fully closed? Actually a cycle is a closed loop where every node has indegree 1 and outdegree 1. So no node has indegree 0. So not possible. So a node with indegree 0 cannot be part of a cycle; it must be the start of a directed path that ends somewhere. So all good.
Thus the algorithm is sound.
Now, but is there any scenario where we have a tank that leads to a sink that is not a tap because the sink has indegree 0? That can't happen because we came from an edge, so sink has at least indegree 1.
Now, let's consider implementation: We'll use int arrays size n+1, initialize to 0.
Potential pitfalls: The problem states p can be 0, up to n. So if p=0, to all zero, indeg all zero. No tanks because out[i]==0. So t=0. Output "0". Should we print a blank line? Just first line 0.
Now, note: The output says "Print integer t in the first line — the number of tank-tap pairs of houses." Then for each line after that, print three integers. So if t=0, we only print the first line.
Now, check example 2: output 0. That's just first line.
Now, check constraints: n up to 1000, fine.
Now, we also need to ensure we handle diameters correctly: diam[i] is defined only if to[i] != 0. So we can store in array.
Now, there is a possible nuance: The problem says "Lulu wants to find the maximal amount of water that can be safely conveyed from each tank to its corresponding tap." That is the minimum capacity along the path. That's what we output.
Now, code.
But there is a subtlety: Could there be multiple tanks that share the same tap? That would require two separate paths converge to the same sink, but that would give the sink indegree at least 2, which is not allowed. So each tap belongs to exactly one tank. So t = number of tanks = number of taps.
Now, what about a node that is a sink but not reachable from a tank? That would mean it has indegree 1 but the source node has indegree maybe 1? Actually if a sink has indegree 1, then there is exactly one incoming edge from some node u. That node u must have outdegree 1 (since it has an outgoing edge to the sink). Could u have indegree 0? Possibly yes, then u is a tank. If u has indegree 1, then it is a middle node. So the chain can be traced back until we find a node with indegree 0. Since each node has at most one incoming, the chain backwards is unique. And eventually we must hit a node with indegree 0 because otherwise we would have an infinite chain or a cycle. But can we have a finite chain where the start node has indegree 1? That would mean the chain is actually a cycle if we go backwards? Let's think: If every node in a chain has indegree 1, then if we start from a sink and go backwards (following the incoming edges), we would continue indefinitely if there's no node with indegree 0. Since the graph is finite, the only way to avoid an infinite chain is to encounter a node that we have already visited, forming a cycle. But a cycle would mean some node has indegree 1 from within the cycle and also we came from outside? Actually if we start at a sink and follow incoming edges, each step we go to the unique predecessor (if any). If we ever revisit a node, we have a cycle. But a cycle in an indegree≤1 graph would have each node indegree 1 from within the cycle, so it's a directed cycle. But if we started from a sink, a sink has outdegree 0, so it cannot be part of a cycle because cycles require outdegree 1. So the backtrack from sink will never cycle because if we ever hit a node in a cycle, that node has indegree 1 from within the cycle, but we are coming from outside the cycle, which would give it a second incoming edge? Actually if there's a cycle, each node in the cycle has indegree 1 (from its predecessor in the cycle). If there is an external node that points to a node in the cycle, that node would then have indegree 2 (one from within cycle, one from external). That's not allowed. So a sink cannot be connected to a cycle. Therefore, backtrack from a sink must eventually reach a node with indegree 0. So every sink is reachable from a tank. So the number of tanks equals number of sinks. So t = number of tanks = number of sinks.
Thus algorithm works.
Now, we should produce output with sorted tanks. Since we iterate i from 1 to n, and only process when tank condition holds, we will output in increasing order automatically if we store in that order. But careful: If we use a vector and push back, the order will be as we encounter tanks: i increasing. So we can just push and then later output without sorting.
One more nuance: The problem says: "All the t lines should be ordered (increasingly) by tanki." So if we process in increasing i, that is satisfied.
Now, check if there is any scenario where multiple tanks could have the same tank? Not possible.
Now, we need to watch for integer overflow? No.
Now, we need to output exactly t lines.
Edge Cases:
-
n=1, p=0: output 0.
-
n=1, p=1? But constraint a ≠ b, so can't have self-loop. So p=0 only.
-
n=2, p=1: 1->2 diam d. Tank=1, Tap=2. Output.
-
n=2, p=2: 1->2 and 2->1 (cycle). No tank/tap. output 0.
-
n=2, p=2: 1->2 and 1->2? Not possible because outdegree of 1 would be 2. So p up to n, but also respecting degree constraints. So p can be at most n, but no node can have two outgoing. So p <= n and each node can have at most one outgoing. So p cannot exceed n. And each node can have at most one incoming.
-
Possibly there can be nodes that have indegree 0 and outdegree 1 but the path length is 0? No.
Now, some implementations may need to handle large diameters: up to 1e6, min calculation with initial large number.
Now, I think that's it.
But let's double-check the traversal logic:
Option: Use while (to[cur] != 0) but we need minD from edges. Better: Start with cur = i, minD = diam[cur] (since edge from cur to to[cur] exists). Then set nxt = to[cur]. While (to[nxt] != 0) { minD = min(minD, diam[nxt]); nxt = to[nxt]; } After loop, tap = nxt. That's correct.
But what about the case where the tank's outgoing pipe goes directly to a sink? then nxt = to[i]; to[nxt] == 0; loop skipped; tap = nxt; minD = diam[i]. Good.
Now, ensure that we are not missing the case where there is a path with a single node? Not possible because pipe connects two distinct houses. So each edge connects two distinct nodes. So path length at least 1.
Now, check the output format: "Print integer t in the first line — the number of tank-tap pairs of houses. For the next t lines, print 3 integers per line, separated by spaces: tanki, tapi, and diameteri, where tanki ≠ tapi (1 ≤ i ≤ t). Here tanki and tapi are indexes of tank and tap houses respectively, and diameteri is the maximum amount of water that can be conveyed." So diameteri is the max safe amount, which is the min diameter along the path. So we output that.
Now, I'd like to test a few more cases.
Case: n=5, p=3: 1->2 (5), 2->3 (3), 4->5 (7). Then tanks: 1 and 4. 1->2->3: min = min(5,3)=3, tap=3. 4->5: min=7, tap=5. Output sorted by tank: 1 3 3, 4 5 7. Good.
Case: n=5, p=4: 1->2 (10), 2->3 (20), 3->4 (5), 4->5 (30). Tank: 1, min = min(10,20,5,30)=5, tap=5. Output: 1 5 5.
Case: cycle plus isolated path: n=6, p=5: 1->2 (10), 2->3 (5), 3->1 (7) (cycle), and 4->5 (8), 5->6 (9). Tanks: 4 (indeg0 out non-zero). So output 4 6 min(8,9)=8? Actually min(8,9)=8. So only one pair. So t=1.
What about a node that is sink but its predecessor is a tank? That's covered.
Now, I'll also consider the possibility of zero-diameter? But di ≥ 1, so positive.
Now, is there any scenario where we need to output something like if the min diameter is zero? No.
Now, I think solution is correct.
But I recall a known Codeforces problem: "Pipes" or "Watering System"? Actually it's Codeforces Round problem "Pipes" maybe? The problem is from Codeforces 107? Wait, I recall a problem "Pipes" in Codeforces Round 1300? Actually there is Codeforces problem "Jzzhu and Children"? Not sure. But anyway.
But hold on, there's a nuance: The problem says "For each house, there is at most one pipe going into it and at most one pipe going out of it." So the graph is a set of chains and cycles. However, the problem also says "Lulu wants to find the maximal amount of water that can be safely conveyed from each tank to its corresponding tap." But if there is a path that has multiple tanks? No.
But there is a twist: The input may include pipes that create cycles, which we ignore. But also, what about houses that have an outgoing pipe but no incoming? That's tank. But what about houses that have an incoming pipe but no outgoing? That's tap. So we output for each tank the corresponding tap. But is there any requirement that the tap must be unique? Yes.
Now, what about a scenario where a house has both an incoming and outgoing? It's a middle house, not tank nor tap. No output.
Now, I think we are done.
But we must be cautious: The problem statement says "For each house, there is at most one pipe going into it and at most one pipe going out of it." So we can rely on that.
Now, let's produce final solution in C++.
Plan:
-
include <bits/stdc++.h>
-
using namespace std;
-
const int N = 1005;
-
int to[N] = {0};
-
int diam[N] = {0};
-
int indeg[N] = {0};
-
int main() { int n, p; cin >> n >> p; for (int i=0; i<p; i++) { int a, b, d; cin >> a >> b >> d; to[a] = b; diam[a] = d; indeg[b]++; } vector<tuple<int,int,int>> res; for (int i=1; i<=n; i++) { if (indeg[i]==0 && to[i]!=0) { // tank int cur = i; int minD = diam[cur]; int nxt = to[cur]; while (to[nxt] != 0) { minD = min(minD, diam[nxt]); nxt = to[nxt]; } int tap = nxt; res.push_back({i, tap, minD}); } } cout << res.size() << endl; for (auto [tank, tap, d] : res) { cout << tank << " " << tap << " " << d << endl; } return 0; }
We used C++17 structured binding.
Now, test with examples.
Example 1: n=3 p=2: to[1]=2 diam[1]=10 indeg[2]=1 to[2]=3 diam[2]=20 indeg[3]=1 Loop: i=1 indeg[1]=0 to[1]!=0 -> cur=1, minD=10, nxt=2, to[2]!=0 -> minD=min(10,20)=10, nxt=to[2]=3, to[3]=0 -> tap=3, push (1,3,10). i=2 indeg[2]=1 skip; i=3 indeg[3]=1 skip. Output: size=1 then 1 3 10. OK.
Example 2: n=3 p=3: Edges: 1->2 d20, 2->3 d10, 3->1 d5. to[1]=2 diam[1]=20 indeg[2]=1; to[2]=3 diam[2]=10 indeg[3]=1; to[3]=1 diam[3]=5 indeg[1]=1. So indeg all 1, no tank. Output 0. OK.
Example 3: n=4 p=2: to[1]=2 diam[1]=60 indeg[2]=1; to[3]=4 diam[3]=50 indeg[4]=1. i=1 tank -> cur=1 minD=60, nxt=2, to[2]=0 -> tap=2, push (1,2,60). i=3 tank -> cur=3 minD=50, nxt=4, to[4]=0 -> tap=4, push (3,4,50). Output size 2 then lines in order: 1 2 60, 3 4 50. OK.
Now, additional tests:
Case: n=5 p=0: No tanks, output 0.
Case: n=5 p=1: 2->3 d100. to[2]=3, indeg[3]=1. i=2: indeg[2]=0 && to[2]!=0 -> tank. minD=100, nxt=3, to[3]==0 -> tap=3, push (2,3,100). Output 1 line: 2 3 100.
But what about i=1? indeg[1]=0, to[1]=0 => not tank.
Now, is there any node that has both indegree 0 and outdegree 0? Not considered.
Now, what about a case where there is a path that ends at a sink that has no outgoing but maybe also indegree 0? Not possible.
Now, I think it's correct.
But wait: There's a nuance: The problem says "For every house with an outgoing water pipe and without an incoming water pipe, Lulu should install a water tank at that house. For every house with an incoming water pipe and without an outgoing water pipe, Lulu should install a water tap at that house." So we are supposed to output pairs where a tank is connected to a tap via a sequence of pipes. So we output (tank, tap, min diameter). That's it.
But the problem also says: "The amount of water each tank conveys should not exceed the diameter of the pipes connecting a tank to its corresponding tap." It might be ambiguous: Could it be that the water from a tank can be split? But since each node has at most one outgoing, there is no splitting; each tank supplies exactly one tap. So it's straightforward.
Now, the only tricky part: Could there be a path where the tank and tap are not directly connected by a sequence? Actually they are.
Now, confirm ordering: sorted by tank increasing.
Now, time to consider potential pitfalls: The while loop condition "to[nxt] != 0" works because we have stored to[] = 0 if no outgoing. But what if nxt is 0? Not possible because to[i] != 0 ensured that to[i] is some positive node. So nxt is positive.
Now, we might need to consider that some node might be both a tank and a sink? Not possible.
Now, everything seems fine.
Now, final check: p ≤ n, but p can be up to n. That's fine.
Now, let's produce final answer.
But I'll also think about an alternative representation: Since the graph is a set of paths, we could also compute by scanning from sinks backward, but our method is simpler.
Now, I'm ready to write final solution.
But wait: The problem statement says: "Lulu wants to find the maximal amount of water that can be safely conveyed from each tank to its corresponding tap." That could be interpreted as: For each tank-tap pair, the maximum water that can flow safely is the minimum diameter on the path. So we output that minimum.
Now, I think it's done.
Now, I'll write the final answer with explanation.
But before finalizing, I'll consider if there is any hidden trap: For a tank, its outgoing pipe is mandatory. But what if the tank also has an incoming pipe? That can't be because it's a tank. So fine.
Now, is there any scenario where the path contains only one pipe and we output the diameter? Yes.
Now, code uses vector of tuples. That's fine.
Now, final code in C++.
But we need to handle the case where n can be 0? No, n>=1.
Now, potential memory: small.
Now, consider if we want to avoid using tuple and use struct, but fine.
Now, final answer: Provide explanation and code.
But perhaps we should test with a custom case:
n=5 p=3: 2->3 (5), 3->4 (6), 4->5 (7). Tank? indeg[2]=0 out[2]=3 => tank. Then path: 2->3->4->5. min=5. Output: 2 5 5.
Now, also node 1 isolated. Output only one pair.
Now, what about a case where there is a node that is a tank and also leads to a node that is a tank? Not possible.
Now, any scenario where we might need to output multiple pairs with same tank? No.
Now, confirm that we must output t lines even if t=0, only first line.
Now, check that we aren't outputting any trailing spaces.
Now, think about input where there is a pipe from a to b but b already has an incoming from elsewhere? Input guarantee ensures that at most one pipe going into each house, so no such conflict.
Now, everything seems fine.
Thus the solution.
Now, I'll produce final answer. ```cpp
#include #include #include using namespace std;
const int N = 1005; int to[N]; // outgoing neighbour, 0 if none int diam[N]; // diameter of that outgoing pipe int indeg[N]; // indegree count
int main() { int n, p; cin >> n >> p;
for (int i = 0; i < p; ++i) { int a, b, d; cin >> a >> b >> d; to[a] = b; diam[a] = d; indeg[b]++; } vector<tuple<int, int, int>> ans; // (tank, tap, min diameter) for (int i = 1; i <= n; ++i) { // a tank must have indegree 0 and an outgoing pipe if (indeg[i] == 0 && to[i] != 0) { int cur = i; int minD = diam[cur]; // first pipe int nxt = to[cur]; // walk along the chain until we hit a house with no outgoing pipe while (to[nxt] != 0) { minD = min(minD, diam[nxt]); nxt = to[nxt]; } int tap = nxt; ans.emplace_back(i, tap, minD); } } cout << ans.size() << '\n'; for (auto [tank, tap, d] : ans) { cout << tank << ' ' << tap << ' ' << d << '\n'; } return 0;}
-