[Solution] GP1. Optimal Graph Partition for Fast Routing (GP1)

 [solution] GP1. Optimal Graph Partition for Fast Routing (GP1)

time limit per test

4 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 R2$R2$. When routers are merged, all existing edges connected to the elements of a large node are preserved. Then all routers outside R2$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 R2$R2$. The intuition behind this is that router R1$R1$ does not need to care how to get R24$R24$ from R21$R21$ if R1$R1$ wants to send a packet to R24$R24$. R1$R1$ just needs to find a path to get its packet to an arbitrary router inside R2$R2$ and then let the routers inside R2$R2$ decide how to get R24$R24$. For routers inside R2$R2$, however, there are still 12$12$ table entries, because they need to know the routes to each other.

We can further merge R31,R32,R33,R34$R31,R32,R33,R34$ into a single node R3$R3$. Then for R1$R1$, we need to store only 6$6$ entries in its routing table. For routers in R3$R3$ or R2$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)$G=(V,E)$, where |V|=N (2≤N≤105)$|V|=N(2\le N\le {10}^5)$, |E|=M (1≤M≤2×105)$|E|=M(1\le M\le 2\times {10}^5)$, V={0,1,…,N−1}$V=\{0,1,\dots ,N-1\}$, E={e=(u,v,w)∣There is an edge between nodes u and v with weight w}.$E=\{e=(u,v,w)\mid \text{There is an edge between nodes }u\text{ and }v\text{ with weight }w\}.$

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

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

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

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

RTsize(v,P)=|P|+|Q|−1,$$RTsize(v,P)=|P|+|Q|-1,$$

where |P|$|P|$ is the number of subsets in P$P$, Q$Q$ is the subset in P$P$ such that v∈Q$v\in Q$. |Q|$|Q|$ is the size of Q$Q$.

The set FE(P)$FE(P)$ of free edges of the partition P$P$ are those edges that are not part of the merged nodes, that is, those edges that connect the merged nodes. w(e)$w(e)$ is the weight of the edge e$e$.

In this subtask, it is necessary to solve a narrowed bi-criteria optimization problem:

• Find an optimal partition P, which minimizes:
  maxv∈VRTsize(v,P);$$\underset{v\in V}{max}RTsize(v,P);$$
• Among all the solutions to criteria 1, choose the partition P that maximizes the total weight of free edges:
  maxP∑e∈FE(P)w(e)$$\underset{P}{max}\sum _{e\in FE(P)}w(e)$$

The term narrowed means that the second criterion is not applied independently, but only to the solutions of the first criterion.

The score for SubTask1 for the ith$i^{th}$ graph is calculated by the formula:

Score1i=Score1(P=P(Gi))=N−[maxv∈VRTsize(v,P)]+∑e∈FE(P)w(e)109.$$Score{1}_i=Score1(P=P(G_i))=N-[\underset{v\in V}{max}RTsize(v,P)]+\frac{\sum _{e\in FE(P)}w(e)}{{10}^9}.$$

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

Score1=∑0.3×Score1i$$Score1=\sum 0.3\times Score{1}_i$$

[solution] GP1. Optimal Graph Partition for Fast Routing (GP1)

Input

The first line contains two integers N$N$ and M$M$ (2≤N≤105;N−1≤M≤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$M$ lines contains three integers ui,vi$u_i,v_i$ and wi$w_i$ (0≤ui, vi≤N−1, ui≠vi, 1≤wi≤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 ui$u_i$ and vi$v_i$ with weight wi$w_i$. ei=(ui,vi,wi)$e_i=(u_i,v_i,w_i)$ is the edge with index i$i$ in the edge set E$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.

 [solution] GP1. Optimal Graph Partition for Fast Routing (GP1)

Output

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

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

[solution] GP1. Optimal Graph Partition for Fast Routing (GP1)

Scoring

During the coding phase, your solutions are tested against pre-tests only. The first 5$5$ of them are open and available for download at the link problem-gp1-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.
3. For multiple test cases, the ranking is performed based on the following formula:
   Score1=∑0.3×Score1i.$$Score1=\sum 0.3\times Score{1}_i.$$
4. Final formula for the "ICPC 2022 Online Challenge powered by HUAWEI - Problem 1":
   FinalScore=Score1+Score2.$$FinalScore=Score1+Score2.$$

 [solution] GP1. Optimal Graph Partition for Fast Routing (GP1)

Examples

input

Copy

4 4
0 1 10
2 3 12
0 2 2
2 1 1

output

Copy

3
1 0
2 1 2
1 3

input

Copy

4 4
0 1 1100
2 3 1120
0 2 1020
2 1 1010

output

Copy

3
1 0
2 1 2
1 3 

[solution] GP1. Optimal Graph Partition for Fast Routing (GP1)

Note

In the first test case the graph is divided into three subsets: {0}$\{0\}$, {1,2}$\{1,2\}$, and {3}$\{3\}$, hence P={{0},{1,2},{3}}$P=\{\{0\},\{1,2\},\{3\}\}$, |P|=3$|P|=3$.

As RTsize(1,P)=|{1,2}|+|P|−1=2+3−1=4$RTsize(1,P)=|\{1,2\}|+|P|-1=2+3-1=4$ is maximum among all nodes.

And edges (0,1,10),(0,2,2),(2,3,12)$(0,1,10),(0,2,2),(2,3,12)$ are free edges of partition P$P$. (2,1,1)$(2,1,1)$ is not a free edge since nodes 2 and 1 are in the same subset {1,2}$\{1,2\}$ from P$P$.From the formula we have:

Score1(P)=4−4+10+2+12109=2.4×10−8$$Score1(P)=4-4+\frac{10+2+12}{{10}^9}=2.4\times {10}^{-8}$$

In the second test case the input graph is almost the same except the edge weights.

So the maximum RTsize$RTsize$ is unchanged and the weight sum of free edges increased.

The Score1$Score1$ for the output will be 0.3×(1100+1120+1020)/109$0.3\times (1100+1120+1020)/{10}^9$ points.