(Live Archive) 3820 - Mr. Thompson's Problem [一般圖最大匹配，縮花演算法，O(n^4)]

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=1821

縮花演算法~

請參考： http://www.csie.ntnu.edu.tw/~u91029/Matching.html#5

My code:

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <set>
using namespace std;

struct Blossom_n4 {
    static const int MAX_N = 206;
    bool adj[MAX_N][MAX_N];
    int n;
    void init(int n) {
        this->n = n;
        memset(adj,0,sizeof(adj));
    }
    void add_edge(int u,int v) {
        adj[u][v] = adj[v][u] = 1;
    }
    int m[MAX_N];  //matching point
    //if m[i] == i --> deleted point
    deque<int> path[MAX_N];  //path from root, only stored even point
    int d[MAX_N];  //odd point or even point
    //0 --> even, 1-->odd, -1--<non-visited
    #define SZ(x) ((int)(x).size())
    queue<int> que;
    void label(int u,int v,int lca_id) {
        for (int i=lca_id+1;SZ(path[u])>i;i++) {
            int now=path[u][i];
            if (d[now] == 1) {
                d[now] = 0;
                que.push(now);
                path[now] = path[v];
                path[now].insert(path[now].end(),path[u].rbegin(),path[u].rend()-i);
            }
        }
    }
    bool BFS(int root) {
        for (int i=0;n>=i;i++) {
            path[i].clear();
        }
        while (!que.empty()) que.pop();
        memset(d,-1,sizeof(d));
        d[root] = 0;
        que.push(root);
        path[root].push_back(root);
        while (SZ(que)) {
            int v=que.front();
            que.pop();
            for (int u=0;n>u;u++) {
                if (adj[v][u] && m[u] != u) {
                    //have edges
                    if (d[u] == -1) {
                        if (m[u] == -1) {
                            //oh great
                            //we can update the alternation path!!!
                            for (int i=0;SZ(path[v])-1>i;i+=2) {
                                m[path[v][i]] = path[v][i+1];
                                m[path[v][i+1]] = path[v][i];
                            }
                            m[u] = v;
                            m[v] = u;
                            return true;
                        }
                        else {
                            //oh no
                            //but we find one more even point
                            int uu=m[u];
                            path[uu] = path[v];
                            path[uu].push_back(u);
                            path[uu].push_back(uu);
                            d[u] = 1;
                            d[uu] = 0;
                            que.push(uu);
                        }
                    }
                    else if (d[u] == 1) {
                        //find an odd point
                        //do nothing
                    }
                    else if (d[u] == 0) {
                        //oh jizz
                        //we find a crossing edge
                        //more even points are allowed
                        int lca_id = 0;
                        while (lca_id < SZ(path[u]) && lca_id < SZ(path[v]) && 
                               path[u][lca_id] == path[v][lca_id]) {
                            lca_id++;
                        }
                        lca_id--;
                        label(u,v,lca_id);
                        label(v,u,lca_id);
                    }
                }
            }
        }
        return false;
    }
    int matching() {
        memset(m,-1,sizeof(m));
        int ret=0;
        for (int i=0;n>i;i++) {
            if (m[i] == -1) {
                if (BFS(i)) {
                    ret++;
                }
                else {
                    m[i] = i;
                }
            }
        }
        return ret;
    }
} sagiri;

const int MAX_N = 206;
int a[MAX_N],b[MAX_N];

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int i=0;n>i;i++) {
            scanf("%d",&a[i]);
        }
        set<int> st;
        for (int j=0;m>j;j++) {
            scanf("%d",&b[j]);
            st.insert(b[j]);
        }
        sagiri.init(n);
        for (int i=0;n>i;i++) {
            for (int j=i+1;n>j;j++) {
                if (st.find(a[i]+a[j]) != st.end()) {
                    sagiri.add_edge(i,j);
                }
            }
        }
        printf("%d\n",sagiri.matching());
    }
}