HBC230861[HAOI2008]移动玩具,广度优先搜索(BFS),搜索Line Graph Matching题解

想要成为编程高手？那就来试试全网最全C++题库，让您在练习中快速成长。

In the mathematical discipline of graph theory, the line graph of a simple undirected weighted graph GGG is another simple undirected weighted graph LLL that represents the adjacency between every two edges in GGG. Precisely speaking, for an undirected weighted graph GGG without loops or multiple edges, its line graph LLL is an undirected weighted graph such that: Each vertex of LLL represents an edge of GGG; Two vertices of LLL are adjacent if and only if their corresponding edges share a common endpoint in GGG, and the weight of such edge between this two vertices is the sum of the weights of their corresponding edges. A maximum weighted matching in a simple undirected weighted graph is defined as a set of edges where no two edges share a common vertex and the sum of the weights of the edges in the set is maximized. Given a simple undirected weighted connected graph GGG, your task is to find the sum of the weights of the edges in the maximum weighted matching of LLL.

In the mathematical discipline of graph theory, the line graph of a simple undirected weighted graph GGG is another simple undirected weighted graph L(G)L(G)L(G) that represents the adjacency between every two edges in GGG. Precisely speaking, for an undirected weighted graph GGG without loops or multiple edges, its line graph L(G)L(G)L(G) is an undirected weighted graph such that: Each vertex of L(G)L(G)L(G) represents an edge of GGG; Two vertices of L(G)L(G)L(G) are adjacent if and only if their corresponding edges share a common endpoint in GGG, and the weight of such edge between this two vertices is the sum of the weights of their corresponding edges. A maximum weighted matching in a simple undirected weighted graph is defined as a set of edges where no two edges share a common vertex and the sum of the weights of the edges in the set is maximized. Given a simple undirected weighted connected graph GGG, your task is to find the sum of the weights of the edges in the maximum weighted matching of L(G)L(G)L(G).

不断学习，不断挑战，才能在编程领域中脱颖而出！全网最全C++题库，助您成为编程高手！

标签： HBC230861[HAOI2008]移动玩具 广度优先搜索(BFS) 搜索Line Graph Matching题解