#P10372. [2021年联测]傅里叶与化学反应

    ID: 9490 传统题 5000ms 888MiB 尝试: 9 已通过: 1 难度: 10 上传者: 标签>CF3000图论数学矩阵多项式计数DP生成函数FFT

[2021年联测]傅里叶与化学反应

题目描述

有 nn 种物质,编号为 0,…,n−10,\ldots,n-1,每种物质恰有一份。给定 mm 种可发生的反应,每种反应用三元组 (u,v,w)(u,v,w) 表示,把物质 uu 和 vv 的各一份消耗掉,并释放 ww 单位热量。反应不产生还能继续参与反应的物质。

要求每种物质恰好参加一次反应。求所有合法反应方案可能释放的不同总热量,并按升序输出。

输入格式

第一行两个整数 n,mn,m。接下来 mm 行,每行三个整数 u,v,wu,v,w。

输出格式

若不存在合法方案,输出一行 YOU ARE IN TROUBLE。

否则第一行一个整数 kk,表示不同的总热量个数。第二行按升序输出这 kk 个总热量。

样例 1

6 7
0 1 0
1 2 1
3 4 1
4 5 1
0 3 0
1 4 1
2 5 0
2
1 2

样例 2

2 1
0 1 3
1
3

样例 3

6 5
0 1 0
1 2 0
1 4 0
2 3 0
2 5 0
YOU ARE IN TROUBLE

数据范围

  • 20%20\% 的数据满足 0≤w≤10\le w\le1。
  • 另外 20%20\% 的数据满足 0≤n≤200\le n\le20。
  • 另外 10%10\% 的数据中任意两种不同物质都可以反应。
  • 另外 40%40\% 的数据中,物质可以划分成两类,同一类中的物质不能彼此反应。其中 20%20\% 的数据满足任意两种不同类的物质都可以反应。
  • 所有数据满足 0≤n≤1000\le n\le100,nn 为偶数,0≤w≤200\le w\le20。任意一对不同的物质至多有一种反应,物质不能与自身反应。

原 PDF 的样例 3 首行多印了一个 0,上面的样例按正式输入格式保留 n,mn,m。

原 PDF 题面