luogu#P10757. [WC2011] 关系挖掘

    ID: 14693 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2011WC/CTSC/集训队提交答案Special Judge

[WC2011] 关系挖掘

题目描述

有人说:“世界上任何两个人最多只需要通过 66 个人就能建立联系”。小 B 对此非常感兴趣,于是着手开展了一些社会网络中关系挖掘的研究工作。

现在小 B 得到了一个包含 NN 个人的社会网络数据,该网络中有 MM 条关系信息。一条关系信息可以表示为 (ai,bi,wi)(a_i, b_i, w_i),表示 aia_ibib_i 两个人之间存在关系,且紧密度为 wiw_iwi>0w_i>0)。现在小 B 希望挑选其中的 KKKNK\leq N)个人作为研究对象,为使研究工作具有较高的可信度,小 B 希望这 KK 个人之间的关系紧密度之和尽量大。

该问题可抽象为:给定一个带权无向图 G=(V,E)G=(V, E) 和整数 KK,目标是求出点集 VV 的一个子集 SS,使得 S=K|S|=K 且使下式最大化:

$$\sum_{(a_i,b_i,w_i)\in E \wedge a_i\in S \wedge b_i \in S} w_i $$

输入格式

这是一道提交答案的试题,在你的目录下有 1010 个输入文件 relation*.in

输入文件的第一行为三个整数 NNMMKK,分别表示给定的社会网络中的点数(人数)、边数(关系数目)以及需要选择的点数(人数)KK

接下来 MM 行,每行三个正整数 aia_ibib_iwiw_i,表示一条边(关系)。所有的点(人)按 11NN 依次编号。

输出格式

对于每一个输入文件,在目录下给出对应的输出文件 relation*.out

输出文件应包含 KK 行,每行一个整数,表示选出的 KK 个人的编号。

3 2 2
1 2 3
1 3 5 
1
3 

提示

【评分标准】

对于每个测试点,如果你没有输出或者输出不合法则得 00 分。

对于每个测试点,我们设有四个评分参数 m1m_1m2m_2m3m_3m4m_4。假设选手选出的 KK 个人之间关系紧密度之和为 cc

  • c>m1c>m_1,得 1212 分;
  • c=m1c=m_1,得 1010 分;
  • m1>cm2m_1>c\geq m_2,得 88 分;
  • m2>cm3m_2>c\geq m_3,得 55 分;
  • m3>cm4m_3>c\geq m_4,得 33 分;
  • c>0c>0,得 11 分;
  • 否则,得 00 分。