二下

資料結構｜HW1

圖問題

題目敘述

題目要求設計一個程式,能夠從輸入的圖形資料中,找出一個最小的節點集合,使得圖中每條邊至少有一個端點包含在這個集合內。

輸入資料的格式為:

第一行是一個整數n,代表這個圖形有n個節點(編號從0到n-1) 接下來有n行,每行有n個0或1,用來表示節點之間的連接關係。第i行第j個數字為1,表示節點i和節點j之間有一條邊相連,為0則表示沒有連接。 輸入資料會連續輸入多組圖形,直到出現一個-1作為結束訊號。 程式需要對於每一組輸入的圖形資料,輸出一個整數,代表最小節點覆蓋集合所包含的節點數量。

舉個例子,假設輸入資料為:

1
2
3

2
0 1
1 0

代表這個圖形有2個節點(0和1),且這兩個節點之間有一條邊相連。對於這個例子,最小節點覆蓋集合可以只包含一個節點(0或1),所以輸出為1。

再舉一個例子,假設輸入為:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

9
0 1 0 0 0 1 0 0 0
1 0 0 1 0 0 0 1 0
0 0 0 0 1 0 0 0 0
0 1 0 0 0 1 1 0 1
0 0 1 0 0 1 0 0 0
1 0 0 1 1 0 0 0 0
0 0 0 1 0 0 0 0 1
0 1 0 0 0 0 0 0 1
0 0 0 1 0 0 1 1 0

對應的最小節點覆蓋集合需要包含3個節點,所以輸出為3。

答題思路

這個題目是要求設計一個演算法程式,能夠從輸入的圖形資料中找出最小節點覆蓋集合的大小,並對於每組輸入資料輸出結果。這是一個經典的組合優化問題,解決方式涉及搜索、貪婪等技術。

參考答案 

 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
41
42
43
44
45

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>

using namespace std;

int minCoveredNodes(vector<vector<int>> &matrix, int n) {
    function<vector<vector<int>>(int, int)> getCombination = [](int n, int k) -> vector<vector<int>> {
        vector<vector<int>> result;
        vector<int> combination;
        function<void(int)> recurCombin = [&](int idx) -> void {
            if(combination.size() == k) { result.push_back(combination); return; }
            for(int i{idx}; i < n; ++i) {
                combination.push_back(i);
                recurCombin(i + 1);
                combination.pop_back();
            }
        };
        recurCombin(0);
        return result;
    };
    function<void(vector<int>&, vector<int>&)> addVec = [](vector<int>& a, vector<int>& b) -> void {
        for(int i{0}; i < a.size(); i++) a[i] += b[i];
    };

    for(int i{1}; i <= n; ++i) {
        for(auto &com : getCombination(n, i)) {
            vector<int> covered(n, 0);
            for(int j{0}; j < i; ++covered[j++]) addVec(covered, matrix[com[j]]);
            if(all_of(covered.begin(), covered.end(), [](int n) { return n > 0; })) return i;
        }
    }
    return n;
}

int main() {
    int n;
    while(cin >> n && n > 0) {
        vector<vector<int>> matrix(n, vector<int>(n, 0));
        for(int i{0}; i < n; i++) for(int j{0}; j < n; j++) cin >> matrix[i][j];
        cout << minCoveredNodes(matrix, n) << endl;
    }
    return 0;
}