MPMB_code/BruteForce.cpp at main · Spockkk0225/MPMB_code · GitHub

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
#include "BruteForce.h"

void BruteForce(Model &model) {
    double ans = 0;
    for (int gen = 0; gen < (1 << model.num_e); gen++) {
        int gen_seed = gen;

        double pr = 1.0;
        model.sampling_neighbor.clear();
        model.sampling_neighbor.resize(model.neighbor.size(), vector<Edge>{});
        for (auto &u: model.node_l) {
            for (auto edge: model.neighbor[u]) {
                if ((gen_seed & 1) == 0) {
                    pr *= edge.pr;
                    model.sampling_neighbor[edge.u].push_back(Edge{edge.u, edge.v, edge.weight, edge.pr});
                    model.sampling_neighbor[edge.v].push_back(Edge{edge.v, edge.u, edge.weight, edge.pr});
                } else {
                    pr *= 1 - edge.pr;
                }
                gen_seed >>= 1;
            }
        }

        ans += pr;
        MaximumButterfly(model, pr);
    }

    cout << "total " << ans << "**" << endl;
    model.fout << "total " << ans << "*" << endl;
    model.PrintResult();
}

void MaximumButterfly(Model &model, double pr) {
    vector<Butterfly> max_butterfly_set;
    double max_weight = 0;
    for (int &u: model.node) {
        unordered_map<int, vector<Angle>> angle;
        for (auto &edge1: model.sampling_neighbor[u]) {
            int v = edge1.v;
            if (model.priority[v] >= model.priority[u]) continue;
            for (auto &edge2: model.sampling_neighbor[v]) {
                int w = edge2.v;
                if (model.priority[w] >= model.priority[u]) continue;

                Angle new_angle = Model::EdgeToAngle(edge1, edge2);
                angle[w].push_back(new_angle);
            }
        }

        for (auto &[w, angles]: angle) {

            for (int i = 0; i < angles.size(); i++) {
                for (int j = i + 1; j < angles.size(); j++) {
                    Butterfly butterfly = Model::AngleToButterfly(angles[i], angles[j]);

                    if (butterfly.weight == max_weight) {
                        max_butterfly_set.push_back(butterfly);
                    } else if (butterfly.weight > max_weight) {
                        max_butterfly_set.clear();
                        max_butterfly_set.push_back(butterfly);
                        max_weight = butterfly.weight;
                    }
                }
            }
        }
    }

    for (auto &butterfly: max_butterfly_set) {
        model.result[butterfly] += pr;
    }
}


void ComputePriority(Model &model) {
    vector<pair<int, int>> value;
    for (int i = 1; i <= model.num_l + model.num_r; i++) {
        value.emplace_back(model.neighbor[i].size(), i);
    }
    sort(value.begin(), value.end());

    model.priority.resize(model.num_l + model.num_r + 1);
    for (int i = 1; i <= model.num_l + model.num_r; i++) {
        model.priority[value[i - 1].second] = i;
    }
}


void MaximumButterfly2(Model &model, double pr) {
    vector<Butterfly> max_butterfly_set;
    int max_weight = 0;
    for (int &u: model.node_l) {
        unordered_map<int, vector<Angle>> angle;
        for (auto &edge1: model.sampling_neighbor[u]) {
            int v = edge1.v;
            for (auto &edge2: model.sampling_neighbor[v]) {
                int w = edge2.v;

                Angle new_angle = Model::EdgeToAngle(edge1, edge2);
                angle[w].push_back(new_angle);
            }
        }

        for (auto &[w, angles]: angle) {

            for (int i = 0; i < angles.size(); i++) {
                for (int j = i + 1; j < angles.size(); j++) {
                    Butterfly butterfly = Model::AngleToButterfly(angles[i], angles[j]);

                    if (butterfly.weight == max_weight) {
                        max_butterfly_set.push_back(butterfly);
                    } else if (butterfly.weight > max_weight) {
                        max_butterfly_set.clear();
                        max_butterfly_set.push_back(butterfly);
                        max_weight = butterfly.weight;
                    }
                }
            }
        }
    }

    for (auto &butterfly: max_butterfly_set) {
        model.result[butterfly] += pr;
    }
}