luogu#P10757. [WC2011] 关系挖掘
[WC2011] 关系挖掘
题目描述
有人说:“世界上任何两个人最多只需要通过 个人就能建立联系”。小 B 对此非常感兴趣,于是着手开展了一些社会网络中关系挖掘的研究工作。
现在小 B 得到了一个包含 个人的社会网络数据,该网络中有 条关系信息。一条关系信息可以表示为 ,表示 与 两个人之间存在关系,且紧密度为 ()。现在小 B 希望挑选其中的 ()个人作为研究对象,为使研究工作具有较高的可信度,小 B 希望这 个人之间的关系紧密度之和尽量大。
该问题可抽象为:给定一个带权无向图 和整数 ,目标是求出点集 的一个子集 ,使得 且使下式最大化:
$$\sum_{(a_i,b_i,w_i)\in E \wedge a_i\in S \wedge b_i \in S} w_i $$输入格式
这是一道提交答案的试题,在你的目录下有 个输入文件 relation*.in
。
输入文件的第一行为三个整数 , 和 ,分别表示给定的社会网络中的点数(人数)、边数(关系数目)以及需要选择的点数(人数)。
接下来 行,每行三个正整数 ,,,表示一条边(关系)。所有的点(人)按 到 依次编号。
输出格式
对于每一个输入文件,在目录下给出对应的输出文件 relation*.out
。
输出文件应包含 行,每行一个整数,表示选出的 个人的编号。
3 2 2
1 2 3
1 3 5
1
3
提示
【评分标准】
对于每个测试点,如果你没有输出或者输出不合法则得 分。
对于每个测试点,我们设有四个评分参数 、、 和 。假设选手选出的 个人之间关系紧密度之和为 ,
- 若 ,得 分;
- 若 ,得 分;
- 若 ,得 分;
- 若 ,得 分;
- 若 ,得 分;
- 若 ,得 分;
- 否则,得 分。