0

これは、「グラフの存在」の問題に関するものです - http://acm.mipt.ru/judge/problems.pl?problem=110。例 1 にはツリーがなく、例 2 にはツリーがある理由を誰かが説明できますか? どちらの例でも、頂点 0、1、2、3 が互いに接続されています。参考までに、問題の説明と例を次に示します。

グラフに距離の行列が表示されます。
このグラフがツリーまたはツリーのセット (フォレスト) であるかどうかを確認する必要があります。
エッジの長さは 0 または正の整数です。

入力: 最初の行には、頂点の数 N が含まれています。
次の N 行には行列が含まれます (行列の左下の三角形のみ)。
距離 -1 は無限距離に対応します。

出力: YES または NO を出力します。YES の場合、次の行にはエッジのリストが含まれている必要があります
木の (与えられた距離行列を持つ任意の木 (森))。
各エッジは、その端の 2 つの識別子によってコード化されます。
頂点識別子は、0、1、...、N-1 の数字です。

入力#1
4
0
1 0
1 1 0
1 1 1 0

出力#1
いいえ

入力#2
5
0
1 0
2 1 0
3 2 1 0
-1 -1 -1 -1 0

出力#2
はい
0 1
1 2
2 3
4

1 に答える 1

1

この問題は、ロシア語の原文からうまく翻訳されていません。

与えられた行列は、結論としてグラフの辺の行列ではなく、距離行列です。各エッジの重みはおそらく 1 ですが、重みが負でないかどうかは完全にはわかりません。マトリックスがツリーまたはフォレストによって実現できるかどうかを確認する必要があります。

つまり、最初の例ではすべての頂点が接続されていますが、2 番目の例では次のようなグラフを実現できます。

    Example 2:
    (0) - (1) - (2) - (3)  (4)

例1のグラフは

    Example 1:
    (0) - (1) - (2) - (3)
     |_____|_____|     |     
     |     |___________|
     |_________________|
于 2012-09-29T14:16:12.760 に答える