#P3094. [Acm BeiJing2012]Peach Blossom Spring

    ID: 2249 传统题 1000ms 512MiB 尝试: 228 已通过: 30 难度: 8 上传者: 标签>难度分类提高+/省选-动态规划子集 DP图论Dijkstra位运算子掩码递推 (s-1)&mask无向连通分量CF2400斯坦纳树

[Acm BeiJing2012]Peach Blossom Spring

桃花源(Peach Blossom Spring)

题目背景

东晋诗人陶渊明在《桃花源记》中写到一个与世隔绝的村庄。村民的先祖为躲避秦时的战乱来到这里,数百年后才有一名渔夫发现他们。后来,人们在村庄遗迹中找到了一份关于修路和避难的文书。

原题 PDF 所附陶渊明画像

题目描述

村里有 nn 座房屋和 mm 条损坏的双向道路。房屋编号为 11 至 nn。最前面的 kk 座房屋各住着一户人家,最后面的 kk 座房屋各有一处避难所。

村民可以修复一些道路,让每户人家都能沿修好的道路到达一处避难所。避难所可以自由分配,但每处至多容纳一户。不同家庭可以共用道路,同一条道路修复一次,费用只计一次。

求能使所有家庭都到达避难所的最小修路费用。

输入格式

第一行包含整数 n,m,kn,m,k(1≤n≤70001\le n\le7000,0≤m≤100000\le m\le10000,1≤k≤51\le k\le5,2k≤n2k\le n)。

接下来 mm 行,每行三个整数 u,v,wu,v,w,表示房屋 u,vu,v 之间有一条道路,修复费用为 ww(1≤u,v≤n1\le u,v\le n,1≤w≤10001\le w\le1000)。

输出格式

输出一行一个整数。有合法方案时输出最小总费用,否则输出 -1。

样例

4 3 1
4 2 10
3 1 9
2 3 10
29
6 7 2
1 5 1000
2 6 1000
1 3 1
2 3 1
3 4 1
4 5 1
4 6 1
5

本地评测对应的题面存档 · UVa 题面 PDF