問題一覧 > 通常問題

No.1981 [Cherry 4th Tune N] アルゴリズムが破滅する例

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : / 解いたユーザー数 81
作問者 : 👑 KazunKazun / テスター : miscalcmiscalc 👑 potato167potato167
1 ProblemId : 4670 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-06-17 20:23:01

問題文

非負整数 $N,K$ が与えられる. 以下の条件を全て満たすグラフは存在するか? 存在するならば, その一例を求め, 出力の説明に沿って出力せよ. 存在しないならば, その旨を報告せよ.

  • 頂点数は $2N$ である. その $2N$ 個の頂点を $X_1, X_2, \dots, X_N, Y_1, Y_2, \dots, Y_N$ とする.
  • 辺の本数を $M$ とする. $i~(1 \leq i \leq M)$ 番目の辺は $X_{a_i}$ と $Y_{b_i}$ を無向辺で結ぶ.
  • 単純グラフである. つまり, $1 \leq i \leq M, 1 \leq j \leq M$ において, $i \neq j$ ならば, $(a_i, b_i) \neq (a_j, b_j)$ である.
  • 完全マッチングが存在する.
  • 以下で説明するアルゴリズム A を実行して得られるマッチングの大きさは $K$ である (ただし, マッチングの大きさとは, マッチングを成す辺の数とする).

アルゴリズム A
$2N$ 個の頂点全てを白で塗る.
$i=1,2, \dots, M$ の順に以下を行う.
    2つの頂点 $X_{a_i}, Y_{b_i}$ が共に白で塗られているならば, $i$ 番目の辺を採用し, 頂点 $X_{a_i}, Y_{b_i}$ を赤で塗り替える.
    そうでない場合, $i$ 番目の辺は採用しない.
採用した辺たちからなるマッチングを出力する.

制約

  • $1 \leq N \leq 500$
  • $0 \leq K \leq N$
  • 入力は全て整数である.

入力

$N$ $K$

出力

条件を満たすようなグラフが存在しない場合, 1行で -1 と出力せよ.

存在する場合, 以下の形式で出力せよ.

$M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$

ただし, 条件を満たすようなグラフが複数存在する場合, そのうちの1つを出力すれば良い.

どちらの場合でも最後に改行を忘れないこと.

サンプル

サンプル1
入力
3 2
出力
4
1 3
2 3
3 1
1 2

この出力によるグラフは以下に対応する. このグラフに対してアルゴリズム A を実行すると以下のようになる.

  • $i=1$ とする. このとき, 頂点 $X_1, Y_3$ は共に白なので, $1$ 番目の辺を採用する. そして, 頂点 $X_1, Y_3$ を赤で塗る.
  • $i=2$ とする. このとき, 頂点 $Y_3$ が赤なので, $2$ 番目の辺は採用しない.
  • $i=3$ とする. このとき, 頂点 $X_3, Y_1$ は共に白なので, $3$ 番目の辺を採用する. そして, 頂点 $X_3, Y_1$ を赤で塗る.
  • $i=4$ とする. このとき, 頂点 $X_1$ が赤なので, $4$ 番目の辺は採用しない.
よって, $1,3$ 番目の辺が採用され, 大きさが $2$ のマッチングが出力される.

サンプル2
入力
46 0
出力
-1

アルゴリズム A を実行する際, $i=1$ のときの辺は必ず採用される. このことから, 出力されるマッチングの大きさが $0$ になることはない.

サンプル3
入力
4 4
出力
16
2 1
1 1
1 3
4 3
2 4
4 2
3 3
1 2
3 4
2 2
4 1
4 4
1 4
2 3
3 1
3 2

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