[Solution] Optimal Graph Partition for Fast Routing (GP2) Codeforces Solution

GP2. Optimal Graph Partition for Fast Routing (GP2)

time limit per test

5 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

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.

For example, in the above figure, there are 12$12$ routers in the network. Each edge has a certain weight. Each router has to store 12$12$ table entries for all possible destinations in the network (including itself). We can merge four nodes in the graph into one large abstract node 𝑅2$R2$. When routers are merged, all existing edges connected to the elements of a large node are preserved. Then all routers outside 𝑅2$R2$ only need to store 9$9$ table entries. Therefore, in this case, we can assign the same "next hop" for all destination routers in 𝑅2$R2$. The intuition behind this is that router 𝑅1$R1$ does not need to care how to get 𝑅24$R24$ from 𝑅21$R21$ if 𝑅1$R1$ wants to send a packet to 𝑅24$R24$. 𝑅1$R1$ just needs to find a path to get its packet to an arbitrary router inside 𝑅2$R2$ and then let the routers inside 𝑅2$R2$ decide how to get 𝑅24$R24$. For routers inside 𝑅2$R2$, however, there are still 12$12$ table entries, because they need to know the routes to each other.

We can further merge 𝑅31,𝑅32,𝑅33,𝑅34$R31,R32,R33,R34$ into a single node 𝑅3$R3$. Then for 𝑅1$R1$, we need to store only 6$6$ entries in its routing table. For routers in 𝑅3$R3$ or 𝑅2$R2$, it only needs to store 9$9$ entries. Your task is to find an optimal partition of the initial graph to minimize the maximum size of the routing table for all routers in the network.

A computer network under consideration is an undirected connected graph 𝐺=(𝑉,𝐸)$G=(V,E)$, where |𝑉|=𝑁 (2≤𝑁≤105)$|V|=N(2\le N\le {10}^5)$, |𝐸|=𝑀 (𝑁−1≤𝑀≤2×105)$|E|=M(N-1\le M\le 2\times {10}^5)$, 𝑉={1,2,…,𝑁}$V=\{1,2,\dots ,N\}$, 𝐸={𝑒=(𝑢,𝑣,𝑤)∣

A partition 𝑃$P$ of the network 𝐺$G$ is a set of non-empty subsets of 𝑉$V$ such that every node 𝑣∈𝑉$v\in V$ belongs to exactly one of these subsets, and the induced sub-graph for each subset in 𝑃$P$ is connected. Here, one subset corresponds to one abstract node mentioned above.

Formally, 𝑃$P$ is a valid partition if and only if 𝑃$P$ is a family of sets that satisfies:

• ∅∉𝑃$\mathrm{\varnothing }\notin P$
• ⋃𝐴∈𝑃𝐴=𝑉$\bigcup _{A\in P}A=V$
• ∀𝐴,𝐵∈𝑃:𝐴≠𝐵⟹𝐴∩𝐵=∅$\mathrm{\forall }A,B\in P:A\ne B⟹A\cap B=\mathrm{\varnothing }$
• ∀𝐴∈𝑃$\mathrm{\forall }A\in P$, the induced subgraph 𝐺[𝐴]$G[A]$ is connected

The routing table size of any node 𝑣$v$ for the corresponding partition 𝑃$P$ is defined by the following equation:

The "next hop" is defined by the shortest path tree. For each node pair (𝑢,𝑣),𝑢∈𝑉,𝑣∈𝑉$(u,v),u\in V,v\in V$, the "next hop" is a node 𝑧∈𝑉$z\in V$, such that there is an edge 𝑒∈𝐸$e\in E$ connected from 𝑢$u$ to 𝑧$z$ directly, and 𝑑𝑖𝑠𝑡(𝑢,𝑣)=𝑤(𝑒)+𝑑𝑖𝑠𝑡(𝑧,𝑣)$dist(u,v)=w(e)+dist(z,v)$, here 𝑑𝑖𝑠𝑡(𝑢,𝑣)$dist(u,v)$ denotes the length of the shortest path from 𝑢$u$ to 𝑣$v$, and 𝑤(𝑒)$w(e)$ denotes the weight of the edge connecting 𝑢$u$ and 𝑧$z$. The valid "next hop" may not be unique. After the graph partitioning, the "next hop" for nodes in the same subset 𝐴∈𝑃$A\in P$ is calculated via the shortest path in the induced sub-graph 𝐺[𝐴]$G[A]$ using the same method above. We compute the "next hop" for two nodes from different subsets of 𝑃$P$ by calculating the shortest path in the "compressed" graph (we compress all nodes in the same subset into a single node). The new graph only contains edges between nodes from different subsets. And then find the shortest path from the subset containing 𝑢$u$ to the subset containing 𝑣$v$. Suppose the first edge in this path is between (𝑥,𝑦)$(x,y)$. From the definition, 𝑥$x$, 𝑦$y$ are in different subsets of 𝑃$P$, and 𝑢$u$ is in the same subset of 𝑥$x$. If 𝑥=𝑢$x=u$, then the "next hop" of (𝑢,𝑣)$(u,v)$ is 𝑦$y$, otherwise the "next hop" of (𝑢,𝑣)$(u,v)$ is the "next hop" of (𝑢,𝑥)$(u,x)$.

The path from 𝑢$u$ to 𝑣$v$ may differ from the path in the graph before partition.

For example:

Originally, the packet transmission path from 1$1$ to 2$2$ is the shortest in the whole graph, so it is 1→3→2$1\to 3\to 2$, and the total length is 3.

If our partition 𝑃={{1,2},{3},{4}}$P=\{\{1,2\},\{3\},\{4\}\}$, then the packet transmission path from 1$1$ to 2$2$ is the shortest path in the subgraph, so it is 1→2$1\to 2$. The total length is 10$10$, which gets much greater after partition.

Define 𝑑𝑖𝑠𝑡(𝑢,𝑣)$dist(u,v)$ as the length of the shortest path from 𝑢$u$ to 𝑣$v$ in graph 𝐺$G$.

Let 𝑐𝑜𝑠𝑡(𝑢,𝑣,𝑃)$cost(u,v,P)$ be the length of the optimal transmission path after dividing graph 𝐺$G$ by partition 𝑃$P$. The way to determine 𝑐𝑜𝑠𝑡(𝑢,𝑣,𝑃)$cost(u,v,P)$ is specified later.

For node 𝑢$u$, we define 𝐵(𝑢,𝑃)=𝑄$B(u,P)=Q$, where 𝑄$Q$ is the unique subset in 𝑃$P$ such that 𝑢∈𝑄$u\in Q$.

Define two new edge sets:

𝐸𝑑𝑔𝑒𝑍𝑒𝑟𝑜(𝑃)={(𝑢,𝑣,𝑤)∣(𝑢,𝑣,𝑤)∈𝐸∧𝐵(𝑢,𝑃)≠𝐵(𝑣,𝑃)}∪Define two undirected weighted graphs: 

𝐺𝑟𝑎𝑝ℎ𝑍𝑒𝑟𝑜(𝑃)=(𝑉,𝐸𝑑𝑔𝑒𝑍𝑒𝑟𝑜(𝑃))$GraphZero(P)=(V,EdgeZero(P))$, 𝐺𝑟𝑎𝑝ℎ𝐼𝑛𝑓(𝑃)=(𝑉,𝐸𝑑𝑔𝑒𝐼𝑛𝑓(𝑃))$GraphInf(P)=(V,EdgeInf(P))$.

In other words, 𝐺𝑟𝑎𝑝ℎ𝑍𝑒𝑟𝑜(𝑃)=(𝑉,𝐸𝑑𝑔𝑒𝑍𝑒𝑟𝑜(𝑃))$GraphZero(P)=(V,EdgeZero(P))$ is almost a copy of the original graph, except for all edges that have both endpoints in the same subset of 𝑃$P$ (their weights are set to 0$0$). 𝐺𝑟𝑎𝑝ℎ𝐼𝑛𝑓(𝑃)=(𝑉,𝐸𝑑𝑔𝑒𝐼𝑛𝑓(𝑃))$GraphInf(P)=(V,EdgeInf(P))$ is also almost a copy of the original graph, except for all edges that connect different subsets of 𝑃$P$ (their weights are set to infinity).

Let 𝑑𝑖𝑠𝑍𝑒𝑟𝑜(𝑢,𝑣,𝑃)$disZero(u,v,P)$ be the length of the shortest path from 𝑢$u$ to 𝑣$v$ in 𝐺𝑟𝑎𝑝ℎ𝑍𝑒𝑟𝑜(𝑃)$GraphZero(P)$.

Let 𝑑𝑖𝑠𝐼𝑛𝑓(𝑢,𝑣,𝑃)$disInf(u,v,P)$ be the length of the shortest path from 𝑢$u$ to 𝑣$v$ in 𝐺𝑟𝑎𝑝ℎ𝐼𝑛𝑓(𝑃)$GraphInf(P)$.

For nodes 𝑢,𝑣: (𝐵(𝑢,𝑃)≠𝐵(𝑣,𝑃))$u,v:(B(u,P)\ne B(v,P))$, we define that 𝑚𝑖𝑑𝑑𝑙𝑒(𝑢,𝑣,𝑃)$middle(u,v,P)$ be the edge 𝑒=(𝑥,𝑦,𝑤)∈𝐸𝑑𝑔𝑒𝑍𝑒𝑟𝑜(𝑃)$e=(x,y,w)\in EdgeZero(P)$ with the samllest edge index which makes the following equation holds:

We can prove such an edge always exists.

Then 𝑐𝑜𝑠𝑡(𝑢,𝑣,𝑃)$cost(u,v,P)$ can be calculated recursively:

• 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)\ne B(v,P))$, let 𝑒=(𝑥,𝑦,𝑤)=𝑚𝑖𝑑𝑑𝑙𝑒(𝑢,𝑣,𝑃)$e=(x,y,w)=middle(u,v,P)$, then 𝑐𝑜𝑠𝑡(𝑢,𝑣,𝑃)=𝑐𝑜𝑠𝑡(𝑢,𝑥,𝑃)+𝑤+𝑐𝑜𝑠𝑡(𝑦,𝑣,𝑃)$cost(u,v,P)=cost(u,x,P)+w+cost(y,v,P)$.

The score for SubTask2 for the 𝑖𝑡ℎ$i^{th}$ graph is calculated by the formula:

The final score for SubTask2 is calculated according to the following formula:

Input

The first line contains two integers 𝑁$N$ and 𝑀$M$ (2≤𝑁≤105;𝑁−1≤𝑀≤2×105)$(2\le N\le {10}^5;N-1\le M\le 2\times {10}^5)$ — the number of nodes and edges, respectively.

Each of the next 𝑀$M$ lines contains three integers 𝑢𝑖,𝑣𝑖$u_i,v_i$ and 𝑤𝑖$w_i$ (0≤𝑢𝑖, 𝑣𝑖≤𝑁−1, 𝑢𝑖≠𝑣𝑖, 1≤𝑤𝑖≤105$0\le u_i,v_i\le N-1,u_i\ne v_i,1\le w_i\le {10}^5$), denoting an edge between the node 𝑢𝑖$u_i$ and 𝑣𝑖$v_i$ with weight 𝑤𝑖$w_i$. 𝑒𝑖=(𝑢𝑖,𝑣𝑖,𝑤𝑖)$e_i=(u_i,v_i,w_i)$ is the edge with index 𝑖$i$ in the edge set 𝐸$E$. It is guaranteed that the input graph is connected and there are no multiple edges. That is, any pair (in any order) of nodes appear in this list no more than once.

The next line contains two numbers: one integer 𝑆𝑒𝑡𝑆𝑖𝑧𝑒$SetSize$ (1≤𝑆𝑒𝑡𝑆𝑖𝑧𝑒≤min(50,𝑁)$1\le SetSize\le min(50,N)$), the size of node set 𝑆$S$ and one real number 𝑘$k$, given with at most six digits after the decimal point (0≤𝑘≤106)$(0\le k\le {10}^6)$.

Each of the next 𝑆𝑒𝑡𝑆𝑖𝑧𝑒$SetSize$ lines contains one integer 𝑁𝑜𝑑𝑒𝐼𝐷$NodeID$ (0≤𝑁𝑜𝑑𝑒𝐼𝐷≤𝑁−1$0\le NodeID\le N-1$), the node in 𝑆$S$.

Output

In the first line, output the number of subsets in your partition 𝑃$P$.

The (𝑖+1)$(i+1)$-th line should begin with a single number 𝑐𝑛𝑡𝑖$cn{t}_i$ — the size of the 𝑖$i$-th subset, followed by 𝑐𝑛𝑡𝑖$cn{t}_i$ numbers, denoting the node IDs in the 𝑖$i$-th subset.

Scoring

During the coding phase, your solutions are tested against pre-tests only. The first 6$6$ of them are open and available for download at the link problem-gp2-open-testset.zip in the "contest materials" section in a sidebar.

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.

1. According to the formula, the solution with a larger score wins.
2. If two solutions have the same score, the solution submitted first wins.