首页 > 代码库 > 二分图搞法

二分图搞法

匈牙利算法

int dfs(int x){    for(int i=1;i<=m;i++){        if(!used[i]&&g[x][i]){            used[i]=1;            if(link[i]==-1||dfs(link[i])){                link[i]=x;                return 1;            }        }    }    return 0;}//用roll的话说就是,找女朋友,如果当前女生已经有男朋友了,就让这个男生去找另外一个女朋友,直到大家都找到为止。若找不到 这个点就没法匹配了。void solve(){    int ans=0;    memset(link,-1,sizeof(link));    for(int i=1;i<=n;i++){        memset(used,0,sizeof(used));        if(dfs(i)) ans++;    }    printf("%d\n",ans);}

二分图的最小顶点覆盖数 = 二分图的最大匹配数

DAG(无回路有向图) 中

DAG图的最小路径覆盖数 = 节点数- 最大匹配数

二分图的最大独立集数 = 节点数 — 最大匹配数

最小点权覆盖: 拆点变成最小割,然后用最大流求解。

最大点权独立集:总权值-最小点权独立集