問題一覧 > 通常問題

No.1773 Love Triangle

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 19
作問者 : hitonanodehitonanode / テスター : ygussanyygussany
7 ProblemId : 7127 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 01:28:33

問題文

本問題は No.1774 Love Triangle (Hard) と「問題設定」「入力の形式や制約」「テストケース数」等が共通していますが,「実行時間制限」「出力形式」「テストケース生成方法」等が異なります.

夜空に光る $N$ 個の星 $1, \dots, N$ があります.相異なる星の三つ組のうち $M$ 個は「大三角」と呼ばれ,$i$ 個目の大三角 $T_i$($1 \le i \le M)$ は星 $(u_i, v_i, w_i)$ $(1 \le u_i < v_i < w_i \le N)$ からなります.

三角形が大好きなあなたはできるだけ多くの大三角を記録に残すため,$\{T_1, \dots, T_M\}$ の部分集合 $S = \{ T_{i_1}, \dots, T_{i_L} \}$ $(1 \le i_1 < i_2 < \dots < i_L \le M)$ を任意に選び,$S$ に含まれる各大三角 $T_{i_l}$ $(l = 1, \dots, L)$ について対応する辺 $(u_{i_l}, v_{i_l})$, $(v_{i_l}, w_{i_l})$, $(w_{i_l}, u_{i_l})$ を張った($N$ 頂点 $3L$ 辺の)無向グラフを作ることにしました.ただし,あなたは三角形だけが好きなので,$S$ は以下の条件を満たさなければなりません:

  • 張られた辺によって長さ $3$ 以外の単純閉路ができてはならない.
  • 特に,多重辺が存在してはならない(選ばれた複数の大三角が辺を共有してはならない).
なお,選んだ大三角同士が(辺ではなく)頂点を共有することは許されます.また,$S$ は空集合や全体集合でも構いません.

上記の条件を全て満たすような $S$ の要素数の最大値を求めてください.

入力

$N\ M$
$u_1\ v_1\ w_1$
$\vdots$
$u_M\ v_M\ w_M$

  • $3 \le N \le 500$
  • $1 \le M \le \min(1000, N(N - 1)(N - 2)/6)$
  • $1 \le u_i < v_i < w_i \le N$ $(i = 1, \dots, M)$
  • $(u_i, v_i, w_i) \ne (u_j, v_j, w_j)$ $(i \ne j)$
  • 入力は全て整数

出力

問題の答えとなる整数を出力してください.末尾で改行してください.

サンプル

サンプル1
入力
8 4
1 2 3
2 4 5
3 5 6
1 3 7
出力
3

$\{T_2, T_3, T_4\}$ は条件を満たし,またこれより要素数が多い集合で条件を満たすものは存在しません.したがって答えは $3$ です.

サンプル2
入力
15 10
5 6 9
6 10 13
3 12 13
2 7 10
3 4 9
2 10 14
2 5 15
1 12 14
1 2 10
8 11 15
出力
7
サンプル3
入力
39 34
6 12 16
5 22 25
4 16 29
27 28 39
17 26 39
31 36 37
16 34 39
13 24 31
2 9 11
3 19 20
32 37 38
4 7 37
34 35 38
1 7 16
11 31 33
4 7 31
2 7 15
9 11 38
16 27 35
28 32 35
14 23 38
4 16 34
3 9 38
16 25 31
14 16 30
4 22 24
12 25 27
20 22 31
8 17 27
19 32 38
14 19 38
3 23 34
3 9 32
10 21 29
出力
18

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。