[solution] GP2. Optimal Graph Partition for Fast Routing (GP2)
- Get link
- X
- Other Apps
[solution] GP2. Optimal Graph Partition for Fast Routing (GP2)
In computer networks, the Internet Protocol (IP) uses path routing. With path routing, the packet contains only the destination address; routers decide which "next hop" to forward each packet on to get it closer to its destination. Each router makes this decision locally, based only on the destination address and its local configuration. One way to store this configuration is to use routing tables, which means for each router, we store the "next hop" for every possible destination. However, as the scale of the network grows larger, the size of the router table grows as well. It is a big issue since routers only have limited computing resources. One way to address this issue is to divide the graph into several partitions.
We can further merge
A computer network under consideration is an undirected connected graph
A partition
[solution] GP2. Optimal Graph Partition for Fast Routing (GP2)
Formally,
∅∉P ⋃A∈PA=V ∀A,B∈P:A≠B⟹A∩B=∅ ∀A∈P , the induced subgraphG[A] is connected
The routing table size of any node
The "next hop" is defined by the shortest path tree. For each node pair
The path from
For example:
Originally, the packet transmission path from
If our partition
Define
Let
For node
[solution] GP2. Optimal Graph Partition for Fast Routing (GP2)
Define two new edge sets:
Define two undirected weighted graphs:
[solution] GP2. Optimal Graph Partition for Fast Routing (GP2)
In other words,
Let
Let
For nodes
We can prove such an edge always exists.
Then
- For nodes
u,v: (B(u,P)=B(v,P)) ,cost(u,v,P)=disInf(u,v,P) . - For nodes
u,v: (B(u,P)≠B(v,P)) , lete=(x,y,w)=middle(u,v,P) , thencost(u,v,P)=cost(u,x,P)+w+cost(y,v,P) .
Given a real number
The score for SubTask2 for the
The final score for SubTask2 is calculated according to the following formula:
The first line contains two integers
Each of the next
The next line contains two numbers: one integer
Each of the next
In the first line, output the number of subsets in your partition
The
During the coding phase, your solutions are tested against pre-tests only. The first
After the end of the coding phase, the last submission that scored a positive number of points on the pre-tests will be selected. It will be retested in the final tests. The rest of your submissions will be ignored. The final tests are secret and not available to the participants, they are mostly realistic. The result obtained on the final tests is your final official result for this problem.
- According to the formula, the solution with a larger score wins.
- If two solutions have the same score, the solution submitted first wins.
- For multiple test cases, the ranking is performed based on the following formula:
Score2=∑0.7×Score2i. - Final formula for the "ICPC 2022 Online Challenge powered by HUAWEI - Problem 1":
FinalScore=Score1+Score2.
4 4 0 1 10 2 3 12 0 2 2 2 1 1 4 0 0 1 2 3
2 2 0 1 2 2 3
4 4 0 1 10 2 3 12 0 2 2 2 1 1 4 2.3 0 1 2 3
2 2 0 1 2 2 3
- Get link
- X
- Other Apps
Comments
Post a Comment