程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 437C The Child and Toy(貪心)

Codeforces 437C The Child and Toy(貪心)

編輯:C++入門知識

題目連接:Codeforces 437C The Child and Toy

題目大意:孩子有一個玩具,有n個部件組成,m條繩子組成,每條繩子連接兩個部件。小孩比較頑皮,要將玩具拆成不可分割的部件,每次剪斷一條繩子的代價是該繩子連接的兩個部件的權值中較小的值。問說最小的總代價是多少。

解題思路:以為每條邊都是要被剪斷的,所以將節點按照代價值從大到小排序,每次拿掉權值大的點,與該點連接並且還未剪斷的邊均用另外點的權值。

#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 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\n", ans);
    return 0;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved