#P9681. The King's Guards

    ID: 6308 传统题 2000ms 512MiB 尝试: 2 已通过: 2 难度: 9 上传者: 标签>CF2800省选/NOI-拟阵贪心Kruskal交换论证二分图建模Kuhn 算法普通并查集增量维护

The King's Guards

题目描述

在 P 国有 nn 个村子,以及 mm 条待修建的双向公路,第 ii 条公路连接 uiu_i 和 viv_i,修建的代价为 wiw_i。

国王找到了 kk 个守卫,每个守卫将入驻一个村子,第 ii 个守卫能入驻的村子是集合 SiS_i。

国王将派遣每个守卫去一个村子,并修建一些公路。

国王希望整个国家得到保护的同时,尽可能节省开支。因此他希望每个村子可以被恰好一个守卫经过若干条公路到达。

国王想要知道,是否存在一种修建公路和派遣守卫的方案,如果存在,修建公路的代价之和最小是多少。

输入格式

第一行三个整数 n,m,kn,m,k,表示村子个数,公路条数和守卫个数。

接下来 mm 行每行三个整数 ui,vi,wiu_i, v_i, w_i 描述了一条公路。

接下来 kk 行,每行 ∣Si∣+1|S_i|+1 个整数,第一个整数 ∣Si∣|S_i| 表示集合大小,接下来 ∣Si∣|S_i| 个整数 si,js_{i,j} 表示集合内容。

输出格式

一行一个整数,如果存在方案输出最小的代价之和,否则输出 -1。

样例

5 6 2
1 2 1
1 3 4
2 4 2
2 5 5
3 4 7
4 5 3
2 1 2
2 2 4
8

修建第 1,2,61,2,6 条道路,两个守卫分别入驻 1,41,4 号村子。

数据范围与提示

本题共 2020 组测试点,各 55 分。

测试点编号 n≤n\le 特殊性质
1∼21\sim 2 66 无
3∼43\sim 4 300300 SiS_i 的大小均为 11
5∼95\sim 9 wi=1w_i=1
10∼1410\sim 14 公路不可能修建出环
15∼2015\sim 20 无

对于所有数据,1≤n≤3001\leq n\leq 300,0≤m≤n(n−1)20\leq m\leq \frac{n(n-1)}{2},1≤k≤n1\leq k\leq n,1≤wi≤10001\leq w_i\leq 1000。

对于所有数据,保证 1≤ui<vi≤n1\leq u_i\lt v_i\leq n,1≤∣Si∣≤n1\leq |S_i|\leq n,1≤si,j≤n1\leq s_{i,j}\leq n,∀i≠j,(ui,vi)≠(uj,vj)\forall i\neq j, (u_i,v_i)\neq (u_j, v_j),∀x,i≠j,sx,i≠sx,j\forall x,i\neq j, s_{x,i}\neq s_{x,j}。