Work Scheduling

板子题，学了个带花树算法。
时间复杂度O(n^3)用于求一般图的最大匹配，即有奇环的图。

struct edge{
    int to,next;
}E[max_m<<1];
int head[max_n];
int cnt=1;
void add(int from,int to){
    E[cnt].to=to;
    E[cnt].next=head[from];
    head[from]=cnt++;
}
int par[max_n],pre[max_n],link[max_n],ans;
deque<int> q;
char ty[max_n];
int findp(int x){return x==par[x]?x:par[x]=findp(par[x]);}
int Ti=0,times[max_n]={};
int lca(int x,int y){
    for(Ti++;times[x]!=Ti;x^=y^=x^=y) 
        if(x) times[x]=Ti,x=findp(pre[link[x]]);
    return x;
}
void blossom(int x,int y,int p){
    while(findp(x)!=p){
        pre[x]=y;
        y=link[x];
        par[x]=par[y]=p;
        if(ty[y]==1) ty[y]=2,q.push_back(y);
        x=pre[y];
    }
}
bool Match(int x,int n){
    for(int i=0;i<=n;i++) ty[i]=0,par[i]=i;
    q.clear();
    ty[x]=2,q.push_back(x);
    while(q.size()){
        x=q.front(),q.pop_front();
        for(int i=head[x];i;i=E[i].next){
            int u = E[i].to;
            if(ty[u]==0){
                ty[u]=1;
                pre[u]=x;
                if(link[u]) q.push_back(link[u]),ty[link[u]]=2;
                else {
                    for(;x;u=x){
                        x=link[pre[u]];
                        link[u]=pre[u];
                        link[link[u]]=u;
                    }
                    return 1;
                }
            }
            else if(ty[u]==2&&findp(u)!=findp(x)){
                int p=lca(x,u);
                blossom(x,u,p),blossom(u,x,p);
            }
        }
    }
    return 0;
}
int Solve(int n){
    int ans=0;
    for(int i=1;i<=n;i++) 
        if(!link[i]&&Match(i,n)) ans++;
    return ans;
}