maximum independent set

ソースコード

 1#include <vector>
 2using namespace std;
 3
 4// MaximumIndependentSet
 5namespace titan23 {
 6    class MaximumIndependentSet {
 7      private:
 8        int n;
 9        vector<vector<bool>> G;
10
11      public:
12        MaximumIndependentSet() : n(-1) {}
13        MaximumIndependentSet(int n) : n(n), G(n, vector<bool>(n, false)) {}
14
15        void add_edge(int u, int v) {
16            G[u][v] = true;
17        }
18
19        vector<int> get_maximum_independent_set() const {
20            const int m = n/2;
21
22            vector<int> dp_s1(m, 1);
23            for (int i = 0; i < m; ++i) {
24                for (int j = 0; j < m; ++j) {
25                    if (G[i][j]) dp_s1[(1<<i)|(1<<j)] = 0;
26                }
27            }
28            for (int s = 0; s < (1<<m); ++s) {
29                if (dp_s1[s]) continue;
30                for (int i = 0; i < m; ++i) {
31                    if ((s >> i & 1) == 0) continue;
32                    for (int j = 0; j < m; ++j) {
33                        dp_s1[s|(1<<j)] = 0;
34                    }
35                }
36            }
37
38            
39
40            for (int s1 = 0; s1 < (1<<m); ++s1) {
41
42            }
43        }
44    };
45} // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/graph/maximum_independent_set.cpp