P10757 [WC2011] Relationship Mining

Some people say, “Any two people in the world can be connected through at most $6$ people.” Little B is very interested in this, so he started some research on relationship mining in social networks. Now Little B has obtained social network testdata containing $N$ people, with $M$ pieces of relationship information. A relationship can be represented as $(a_i, b_i, w_i)$, meaning that there is a relationship between people $a_i$ and $b_i$, and the closeness is $w_i$ ($w_i>0$). Little B now wants to choose $K$ people ($K\leq N$) as research targets. To make the research more reliable, he hopes that the total closeness of relationships among these $K$ people is as large as possible. This problem can be abstracted as: given a weighted undirected graph $G=(V, E)$ and an integer $K$, the goal is to find a subset $S$ of the vertex set $V$ such that $|S|=K$ and the following expression is maximized: $$\sum_{(a_i,b_i,w_i)\in E \wedge a_i\in S \wedge b_i \in S} w_i$$

This is an output-only problem. There are $10$ input files `relation*.in` in your directory. The first line of each input file contains three integers $N$, $M$, and $K$, representing the number of vertices (people), the number of edges (relationships), and the number of vertices (people) to select, $K$, in the given social network. The next $M$ lines each contain three positive integers $a_i$, $b_i$, $w_i$, describing an edge (relationship). All vertices (people) are numbered from $1$ to $N$.

For each input file, provide the corresponding output file `relation*.out` in the directory. The output file should contain $K$ lines, each with one integer, indicating the index of one of the selected $K$ people.

**Scoring.** For each test point, if you do not output anything or your output is invalid, you get $0$ points. For each test point, there are four scoring parameters $m_1$, $m_2$, $m_3$, and $m_4$. Suppose the sum of closeness values among the $K$ people selected by the contestant is $c$. - If $c>m_1$, you get $12$ points. - If $c=m_1$, you get $10$ points. - If $m_1>c\geq m_2$, you get $8$ points. - If $m_2>c\geq m_3$, you get $5$ points. - If $m_3>c\geq m_4$, you get $3$ points. - If $c>0$, you get $1$ point. - Otherwise, you get $0$ points. Translated by ChatGPT 5