Tìm chi phí nhỏ nhất để ngắt kết nối đồ thị

2017-07-19
Bài gốc

Codeforces 437C

Đề bài

Cho đồ thị vô hướng n đỉnh và m cạnh, không có quá một cạnh giữa hai đỉnh bất kì. Mỗi đỉnh i có một giá trị nguyên vi; để loại bỏ đỉnh i cần chi phí , với j là đỉnh kết nối trực tiếp với i và chưa bị loại bỏ.

Tìm chi phí nhỏ nhất để ngắt kết nối toàn đồ thị (loại bỏ các đỉnh đến khi không còn cạnh nào).

Giới hạn:

  • 1 ≤ n ≤ 1000; 0 ≤ m ≤ 2000
  • 0 ≤ vi ≤ 105
Định dạng test

Input:

  • Dòng đầu là n và m.
  • Dòng thứ hai là n số vi.
  • Tiếp theo là m dòng, mỗi dòng là x và y, cho biết có kết nối giữa đỉnh x và đỉnh y.

Các đỉnh được đánh số từ 1 đến n.

Output:

  • Một dòng duy nhất là chi phí tối thiểu.
Thuật toán

Xoá các đỉnh theo thứ tự giảm dần giá trị v của chúng.

Chứng minh: xét cạnh (x, y), khi cạnh này bị xoá thì vx hoặc vy được cộng vào tổng chi phí.

=> Nếu ta xoá đỉnh theo thứ tự giảm dần v, thì min(vx,vy) được cộng vào => thu được chi phí tối thiểu.

Source code

Ngôn ngữ: C++.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

const int N = 1000 + 5;
int n, m, a[N][N], cost[N], id[N];

bool cmp(int i, int j) {
    return cost[i] > cost[j];
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    FOR(i,1,n) {
        cin >> cost[i];
        id[i] = i;
    }
    sort(id + 1, id + n + 1, cmp);

    FOR(i,1,m) {
        int u, v; cin >> u >> v;
        a[u][v] = a[v][u] = 1;
    }

    int res = 0;
    FOR(i,1,n) {
        int u = id[i];

        int t = 0;
        FOR(v,1,n)
            if (a[u][v] == 1) {
                t += cost[v];
                a[u][v] = a[v][u] = 0;
            }
        res += t;
    }
    cout << res;

    return 0;
}
Độ phức tạp

O(Nlog(N) + N2)