Codeforces 437 C The Child and Toy(欲張り)
5629 ワード
タイトル接続:Codeforces 437 C The Child and Toy
子供は1つのおもちゃがあって、nの部品の构成があって、m本の縄の构成、1本の縄は2つの部品をつなぎます.子供はいたずらっ子で、おもちゃを分割できない部品に分解し、1本のロープを切るたびにそのロープが接続されている2つの部品の重み値の中で小さい値になります.最小の総代価はいくらですか.
解題構想:各エッジは切断されると考えられるので,ノードを代価値の大きいものから小さいものに並べ替え,重みの大きい点を毎回取り除き,その点に接続され,まだ切断されていないエッジは別の点の重み値を用いる.
子供は1つのおもちゃがあって、nの部品の构成があって、m本の縄の构成、1本の縄は2つの部品をつなぎます.子供はいたずらっ子で、おもちゃを分割できない部品に分解し、1本のロープを切るたびにそのロープが接続されている2つの部品の重み値の中で小さい値になります.最小の総代価はいくらですか.
解題構想:各エッジは切断されると考えられるので,ノードを代価値の大きいものから小さいものに並べ替え,重みの大きい点を毎回取り除き,その点に接続され,まだ切断されていないエッジは別の点の重み値を用いる.
#include
#include
#include
#include
using namespace std;
const int N = 1005;
const int M = 2005;
struct state {
int id;
int val;
}p[N];
int n, m, v[N], val[N];
vector<int> g[N];
inline bool cmp (const state& a, const state& b) {
return a.val > b.val;
}
void init () {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &val[i]);
p[i].id = i;
p[i].val = val[i];
}
sort(p + 1, p + n + 1, cmp);
int a, b;
for (int i = 0; i < m; i++) {
scanf("%d%d", &a, &b);
g[a].push_back(b);
g[b].push_back(a);
}
}
int main () {
init();
int ans = 0;
memset(v, 0, sizeof(v));
for (int i = 1; i <= n; i++) {
int u = p[i].id;
v[u] = 1;
for (int j = 0; j < g[u].size(); j++) {
int vi = g[u][j];
if (v[vi])
continue;
ans += val[vi];
}
}
printf("%d
", ans);
return 0;
}