0

まず第一に、私はコードや完全な解決策を求めていないことを述べます。 問題について説明します。

建物内の部屋の数とそれらの間の廊下の数が与えられます。すべての廊下は2つの部屋を接続し、重みが与えられます。どの部屋にもいつでも行くことができます。あなたはそれらを取り除くことによってすべての廊下の完全な重量を減らすことになっています、そして減らされた重量を印刷します。

これらの仮定は正しいですか？：

  1. 建物はグラフであり、部屋は頂点であり、廊下はそれらを接続するエッジです。したがって、これは無向連結グラフです。

  2. これを解決するには、グラフの最小スパニングツリーの重みを取得し、完全な重みからMSTの重みを引いたものを実行します。結果は、削除できる廊下の重みの合計になります。

私はMSTにプリムのアルゴリズムを実装しました。結果は、例のケースとインターネットで見つけたMSTの他のケースに対して正しいものです。ただし、グレーディングサーバーは、他の情報がないまま「間違った答え」を返します。何が悪いのかわかりません。入力には100個以下の頂点と5000個のエッジがあるため、範囲は問題になりません。重みは整数<=200です。MTSに隣接行列を使用しています。入力例：

5 7  
1 2 50  
2 3 40  
3 4 20  
4 5 10  
1 4 40  
3 5 30

この場合、プログラムは80を出力します。完全な重みは190、最小の重みは110なので、190-110=80を削除できます。

私の質問は次のとおりです。

  1. 頭に浮かぶ明らかな間違いはありますか？注意すべき点、入力例などで機能するのはなぜですか。
  2. 問題を見つけるために使用できるインターネット上のMSTの中規模のテストケースはありますか？
  3. この問題を解決する他の方法はありますか？採点サーバーで何でも喜んでやってみます。

私はグラフにまったく慣れていないので、何かが足りないかもしれません。

4

1 に答える 1

0
  1. 建物はグラフであり、部屋は頂点であり、廊下はそれらを接続するエッジです。したがって、これは無向連結グラフです。
  2. これを解決するには、グラフの最小スパニングツリーの重みを取得し、完全な重みからMSTの重みを引いたものを実行します。結果は、削除できる廊下の重みの合計になります。

はい、これらは両方とも正しいです（建物が頂点としての部屋とエッジとしての廊下を備えたグラフではないが、そのように表示できるという点を法として）。このように表示すると、元のグラフの総重量と最小スパニングツリーの総重量の差は、一部の部屋が他の部屋から到達できなくなる（つまり、グラフが切断される）ことなく、可能な限り最大の重量削減になります。

だから私は2つの可能性を見ます、

  1. プリムのアルゴリズムの実装に微妙なバグがあります。これは、グレーディングサーバーのテストケースによってトリガーされますが、チェックしたテストケースによってはトリガーされません。
  2. グレーディングサーバーの答えが間違っています。

これ以上の情報がなければ、1つの可能性が高いと思います。

この問題を解決する他の方法はありますか？採点サーバーで何でも喜んでやってみます。

MSTの重みを見つける必要があるので、MSTを見つけずにそれを行う方法がわかりません。したがって、他の方法は、MSTを見つけるための異なるアルゴリズムです。クラスカルのアルゴリズムが思い浮かびます。

于 2013-03-03T21:39:13.530 に答える