UOJ Logo

NOI.AC

#89. 最大割

统计

题目描述

​ 老虎和蒜头是好朋友。

​ 老虎最近迷上了最小割问题和网络流理论。每天老虎写题都一定会写网络流,并坚信网络流是世界万物的真谛,正如调和级数收敛于 $ 400 $ 一样,这世界上的一切问题都是可以通过网络流解决的。

​ 蒜头认为老虎不够清醒,因此他打算给老虎出一道题考验他。但蒜头出完题后老虎不服气,因此他将解答的任务交给了你,希望你能说服老虎。

​ 给一个 $ n $ 个点 $ m $ 条边的有边权的无向图,你的任务是找到一个至少 $13$ 个点的简单环将图划分成两个集合 $S$ 和 $T$ (可以为空)、并最小化 $S$ 内部的边权和加上 $T$ 内部的边权和。

一条边被称为在一个集合内部,当且仅当该边的两个节点都在集合中

输入格式

​ 输入的第一行包括两个正整数 $ n, m $ 。

​ 接下来的 $ m $ 行,每行包括三个整数,表示无向图的一条边 $ (u_i, v_i, c_i) $ ,其中 $ c_i $ 表示边权。

输出格式

​ 输出的第一行应当输出一个字符串 cycle 或是 cut

​ 如果你在第一行输出的是 cycle,那么你应当在接下来的一行输出你找到的简单环的点数 $ k $ ,并在随后的一行按顺序输出 $ k $ 个整数表示环上的点。

​ 如果你在第一行输出的是 cut ,那么你应当在接下来的一行输出你得到的最优解 ans。

样例

样例一

input

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

output

cut
4

样例二

input

13 13
1 2 10
2 3 10
3 4 10
4 5 10
5 6 10
6 7 10
7 8 3
8 9 10
9 10 10
10 11 10
11 12 10
12 13 10
13 1 10

output 1

cut
3

output 2

cycle
13
1 2 3 4 5 6 7 8 9 10 11 12 13

数据范围及限制

对于 100% 的数据,$ 1 \le n \le 2000, 1 \le m \le 4000, 1 \le c_i \le 10000 $ 。

本题采用子任务测试,共包括四个子任务:

Subtask 1[20 分]: $ 1 \le n \le 20 $

Subtask 2[20 分]: $ 1 \le n \le 50 $

Subtask 3[30 分]: $ m \le n + 12 $

Subtask 4[30 分]: 无特殊限制

时间限制: 1s

空间限制: 512MB

样例数据下载