QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 256 MB Total points: 100 Hackable ✓
[0]

# 5365. 修路

Statistics

小针是 C 市的中考状元,他的父亲网友是C市市长。

C 市正在修路,C市共有 2n 个居民点,m 条道路,每条道路连接两个居民点 uv,满足 1un, n+1v2n。现在 C 市需要选择一些道路进行维修,进行维修的道路不能通行。C 市的市民认为,如果某个居民点不能通过可以通行的道路走到其他点,那么生活在这个居民点是非常无趣的,他们就会在网上狂喷网友从而让网友的儿子小针很没面子。C 市的市民还认为,如果修路开始后和某个居民点与大于 k 条没有被维修的道路直接相连,那么这个居民点就会变得过于吵闹,他们还是会在网上狂喷网友从而让网友的儿子小针很没面子。此外,如果某个居民点的市民从自己家开始,经过不重复的道路后回到了自己原来的居民点,这些市民就会很迷茫,他们还是会在网上狂喷网友从而让网友的儿子小针很没面子。为了方便管理市民,网友希望把市民分成尽量多的组,使得组与组之间的市民不能通过可以通行的道路到达

小针发现,每条路的风景都是不一样的,第 i 条路的风景可以用一个正整数 wi 描述。由于小针有私人飞机,他可以无视道路直接到达某个顶点,但是一条路正在维修,小针就无法在这条路上赏风景。他希望没有被维修的道路的总风景值最大。当然,他不能违抗他爸爸的意愿,他也不想没面子。现在小针找到你,希望你能帮他计算一下,没被维修的道路的总风景值最大能达到多少。

输入格式

第一行三个正整数 nmk

以下 m 行每行三个正整数 ui,vi,wi,保证 1uin,n+1vi2n 表示一条边连接第 ui 个和第 vi 个居民点,风景值为 wi

输入数据保证任意两个居民点之间至多只有一条道路。

输出格式

一行两个正整数,表示维修的道路数量和最大总风景值。

如果无论选择修哪些道路,小针都很没面子,输出"FACELESS"(不含引号)

样例数据

样例 1 输入

3 5 2
1 4 1
1 5 2
1 6 3
2 4 4
2 5 5

样例 1 输出

FACELESS

样例 2 输入

3 4 2
1 4 1
2 4 2
3 5 3
3 6 4

样例 2 输出

0 10

子任务

评测采用子任务制,为了拿到某个子任务的分数,必须通过这个子任务的所有数据。

Subtask1 [8pts]: n10,m20

Subtask2 [30pts]: k=2

Subtask3 [30pts]: k=n

Subtask4 [32pts]: 无特殊条件

在以上所有subtask中,1kn1001m20000w10000.