二分图练习1

void dfs(int u)//判断是否是二分图
{
    for(int i=head[u];i;i=edge[i].nx)
    {
        v=edge[i].to;
        if(!dff[v]) dff[v]=0-dff[u],dfs(v);//dff[u]=1,dff[v]=-1,代表两个在不同的集合
        if(dff[v]==dff[u]) return error();
    }
}

推荐博客（讲解匈牙利算法的一般应用）：https://blog.csdn.net/A_Bright_CH/article/details/68486096 

定义：（https://www.cnblogs.com/jianglangcaijin/p/6035945.html）

匈牙利算法的一般用途：1、最大匹配问题

poj1274

2、最小点覆盖问题  最小点覆盖数=最大匹配数（https://blog.csdn.net/rgndao/article/details/102233191）

/ Vijos / 题库 /

CoVH之柯南开锁

#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#include<map>
using namespace std;
#define maxn 500
int match[maxn],n,m,line[maxn][maxn],used[maxn];
char ch[maxn];
bool dfs(int x)
{
    for(int i=1;i<=m;i++)
    {
        if(line[x][i]&&!used[i]){
            used[i]=1;
            if(match[i]==0||dfs(match[i])){
                match[i]=x;
                return true;
            }
        }
    }
    return false;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>ch;
        for(int j=0;j<m;j++)
            if(ch[j]=='1') line[i][j+1]=1;
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        memset(used,0,sizeof(used));
        if(dfs(i)) ++ans;
    }
    cout<<ans;
    return 0;
}

3、最大独立集

最大独立集点数= 总点数 - 最小点覆盖 = 总点数 - 最大匹配数