In optical communication networks, appropriate path planning can improve the utilization of communication resources and bring a smooth communication experience to users. The following figure shows an inter-satellite optical communication network. User messages are sent from one terrestrial base station (nodes $$$4$$$ to $$$7$$$) and transmitted through satellites (nodes $$$0$$$ to $$$3$$$) in space to another terrestrial base station (nodes $$$4$$$ to $$$7$$$).
In the preceding figures, there are communication connections (edges for short) between base stations and satellites and between satellites. The base stations and satellites are referred to as nodes.
User messages are transmitted on these edges and referred to as flows. Some users may make video calls with friends, and some users may send short messages to their family members. Therefore, the message traffic (called flow rate) of each user differs.
There are many parallel edges (for example, edges $$$0$$$, $$$1$$$, and $$$2$$$) between two nodes, and the capacity of each edge also differs. Larger capacity indicates that more user messages can be transmitted, as well as shorter transmission distance indicates lower latency and better communication quality.
Nodes also have their internal structure. As shown below, some edges inside a node cannot communicate with each other because these edges (constrained edge pair) are not fully connected. For example, edge $$$5$$$ and edge $$$7$$$ inside node $$$2$$$ cannot communicate with each other, and therefore flows cannot pass through node $$$2$$$ by traversing the two unconnected edges.
Now, in the input network, the source node, target node, and required flow rate for each user flow are specified. Because network resources are limited, paths may not be successfully calculated for all user flows. We hope that you can provide a solution with the highest score.
Note, that
Constraints
The first line contains four integers separated by space: $$$\mathit{NodeCount}$$$, $$$\mathit{EdgeCount}$$$, $$$\mathit{ConstrainedCount}$$$, and $$$\mathit{FlowCount}$$$.
The next $$$\mathit{EdgeCount}$$$ lines contain information about the network. Each line contains six integers: $$$\mathit{EdgeID}$$$, $$$\mathit{GroupID}$$$, $$$\mathit{StartNodeID}$$$, $$$\mathit{EndNodeID}$$$, $$$\mathit{Distance}$$$, and $$$\mathit{Capacity}$$$.
It's guaranteed that only multiple edges may share the same $$$\mathit{GroupID}$$$.
The next $$$\mathit{ConstrainedCount}$$$ lines contain information about the edge pairs that are not connected in the specified nodes of the network. All other edges are connected to each other by default. Each line contains three integers: $$$\mathit{NodeID}$$$, $$$\mathit{EdgeID}_1$$$, and $$$\mathit{EdgeID}_2$$$.
The next $$$\mathit{FlowCount}$$$ lines contain information about the flows to be calculated. Each line contains four integers: $$$\mathit{FlowID}$$$, $$$\mathit{SourceNode}$$$, $$$\mathit{TargetNode}$$$, and $$$\mathit{FlowRate}$$$.
Don't forget that the $$$\mathit{SFL}$$$ and $$$\mathit{GFL}$$$ mentioned above are also important parameters.
For the simplicity, both $$$\mathit{EdgeID}$$$ and $$$\mathit{FlowID}$$$ of the $$$i$$$-th ($$$0$$$-indexed) edge (flow) is always equal to $$$i$$$.
In the first line, output the number of your success flows.
Next, each line output edge information about the path that a flow passes through.
The format is as follows: $$$\mathit{FlowID}\ \mathit{EdgeID}_1\ \mathit{EdgeID}_2\ \mathit{EdgeID}_3\ \dots\ \mathit{EdgeID}_n$$$.
There is no requirement on the output sequence between flow paths, but edges in one flow must be outputted in order, from source node to target node. Please output all successfully calculated flow paths. For other flows that are not output, the checker determines that you have not found appropriate paths for the flows by default.
8 15 3 1 0 0 0 1 100 1050 1 1 0 1 200 2200 2 1 0 1 200 99400 3 2 0 3 100 450 4 3 0 3 500 1120 5 4 1 2 1000 40000 6 5 2 3 600 10000 7 5 2 3 600 10000 8 6 1 4 120 2500 9 6 1 4 120 450 10 7 1 5 170 1250 11 8 2 5 200 2500 12 9 3 5 100 1250 13 10 3 6 300 1150 14 11 3 7 300 1100 2 5 7 2 6 7 2 6 11 0 4 6 100
1 0 8 0 3 13
The total distance of a flow path is $$$620$$$ ($$$120 + 100 + 100 + 300 = 620$$$). (Note: 0 9 10 12 13 is also a valid output result.)
Name |
---|