問題一覧 > 通常問題

No.1774 Love Triangle (Hard)

レベル : / 実行時間制限 : 1ケース 8.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 3
作問者 : 👑 hitonanodehitonanode / テスター : 👑 ygussanyygussany
2 ProblemId : 7042 / 自分の提出
問題文最終更新日: 2021-12-02 12:34:35

問題文

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

夜空に光る $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_k\}$ の部分集合 $S = \{ T_{i_1}, \dots, T_{i_L} \}$ $(1 \le i_1 < i_2 < \dots < i_L \le k)$ を任意に選び,$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$ の要素数の最大値を求めてください.$k = 1, \dots, M$ の各 $k$ についてそれぞれ問題を解き,各問題の答えを $M$ 行にわたって出力してください.

入力

$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)$
  • 入力は全て整数

出力

$M$ 行にわたって出力してください.$i$ 行目 $(1 \le i \le M)$ には $k = i$ のときの問題の答えとなる整数を出力してください.$M$ 行目の末尾でも改行してください.

サンプル

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

$k = 1$ のとき $\{T_1\}$,$k = 2$ のとき $\{T_1, T_2\}$ はそれぞれ条件を満たす最大の大三角の集合です.

$k = 3$ のとき,$\{T_1, T_2, T_3\}$ という集合を選ぶと,$1 \rightarrow 2 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 1$ などの長さが $3$ でない単純閉路ができてしまい,これは条件を満たしません.したがって,$k = 3$ のときの答えは $k = 2$ のときと同じく $2$ です.

$k = 4$ のとき,$\{T_2, T_3, T_4\}$ は条件を満たし,またこれより要素数が多い集合で条件を満たすものは存在しません.したがって $k = 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
出力
1
2
3
4
4
4
5
6
6
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
出力
1
2
3
4
5
6
7
8
9
10
11
12
12
13
14
14
14
14
14
14
15
15
16
16
17
17
17
17
17
17
17
17
17
18

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