Codeforces ラウンド #250 ディビジョン2(C.子供とおもちゃ)_html/css_WEB-ITnose

题目如下：

C. 子供とおもちゃ

テストごとの制限時間

1 秒

テストごとのメモリ制限

256 メガバイト

入力

標準入力

出力

標準出力

こどもの日に、子供はプレゼントとしてDelayyyからおもちゃをもらいました。しかし、その子供はとてもいたずらなので、おもちゃを壊すのが待ちきれません

おもちゃはn個のパーツとm個のロープで構成されています。各ロープは 2 つのパーツを接続しますが、各パーツのペアは最大でも 1 本のロープで接続されます。おもちゃを分割するには、子供はすべての部品を取り外す必要があります。子供は一度に 1 つの部品を取り外すことができ、取り外すたびにエネルギーを消費します。パート i のエネルギー値を vi として定義しましょう。子供はパーツ i を取り除くために vf1?+?vf2?+?...?+?vfk エネルギーを費やします。ここで、f1、?f2、?...、?fk は i 番目と避難所に直接接続されているパーツです。取り外されていません。

n 個の部品をすべて取り外すのに費やす必要がある最小総エネルギーはいくらか、子供が調べられるように手伝ってください。

入力

最初の行には、2 つの整数 n と m (1?≤?) が含まれています。 n?≤?1000; 0?≤?m?≤?2000）。 2 行目には n 個の整数が含まれています: v1,?v2,?...,?vn (0?≤?vi?≤?105)。その後 m 行が続き、各行には 2 つの整数 xi と yi が含まれており、xi の部分から yi の部分へのロープを表します (1?≤?xi,?yi?≤?n; xi?≠?yi)。

すべての部分を考慮します。 1 から n まで番号が付けられています。

出力

おもちゃの n 個の部分をすべて取り除くのに子供が費やす必要がある最小の総エネルギーを出力します。

サンプルテスト

入力

4 310 20 30 401 41 22 3

出力

40

入力

4 4100 100 100 1001 22 32 43 4

出力

400

入力

7 1040 10 20 10 20 80 401 54 74 55 25 76 41 61 34 31 4

出力

160

注意

最初のサンプルのアクションの最適なシーケンスの 1 つは次のとおりです:

まず、パート 3 を削除します。アクションのコストは 20 です。

次に、パート 2 を削除します。アクションのコストは 10 です。

次に、パート 4 を削除します。アクションのコストは 10 です。

最後に、パート 3 を削除します。アクションのコストは 10 です。パート 1、アクションのコストは 0 です。

したがって、子供が支払ったエネルギーの合計は、20?+?10?+?10?+?0?=?40 で、これが最小値です。

2 番目のサンプルでは、どのような順序で部品を取り外すかに関係なく、子供は 400 を費やします。 2 つの点を接続すると、すべてのコストを考慮した最小値が求められ、1 つの図が形成されます (複数の子図が含まれる場合があります)。そのとき、これらのことは、ある順序に従って取り除かれることが予想されますが（たとえば、心）、私たちはその順序に到達するだけで、その後すべてのコストがかかり、それが結果となります。注意深く分析すると、要求されるのは最小値であり、順序を求める必要はない。つまり、どのような順序でこれらの境界を削除する必要もなく、すべての境界が削除された時点で最終的な結果が得られます。各条の境界を離れるとき、都市には 1 つの代価コストがあり、必然的に接続されている 2 つの点の値のうち最小のものを選択します (一条の接続の 2 つの点は A と B です、境界を離れるとき、値を選択します (A ) と値 (B) 内の小さい値を代価として使用し、すべてのコストを取り除き、すべてのコストを追加するのが最終的な解決策です。

#include <iostream> using namespace std; int main(){	int n, m, v[1024], res = 0, x, y ; 	cin >> n >> m ;	for(int i = 1; i <= n; i++)		cin >> v[i] ; 	while(m--)	{		cin >> x >> y ; 		res += min(v[x], v[y]) ; 	}	cout << res << endl ;	return 0 ; }

この問題報告诉我们，看似的杂的問題，後往往都有一箪简的规律。