学步园

题目 http://acm.hdu.edu.cn/showproblem.php?pid=2444

关键这个问题你要知道什么是二分   就是一条直线相连的二个点  一个在集合A  另一个在B   所以你首先判断是不是二分  可以用二种颜色来区别哦  。

求最大匹配 你可以把A B 集合看成是一个集合哦   然后来计算这个集合的最大匹配

#include <iostream>
using namespace std;

const int M=201;
bool g[M][M]; //图
bool visit[M];  //标记
bool flag;
int  link[M];  //标记那个与那个相连
int  c[M];   //表示颜色，0表示没访问，1表示黑色，-1表示白色
int  n,k;

void dfs(int i,int color)//染色法判断是否是二分图
{
    for(int j=1;j<=n;j++)
    {
        if(g[i][j])
        {
            if(c[j]==0)
            {
                c[j]=-color;
                dfs(j,-color);
            }
            else if(c[j]==color)
            {
                flag=false;
                return;
            }
            if(flag==false)
                return ;
        }
    }
}

bool check()
{
    flag=true;
    memset(c,0,sizeof(c));
    c[1]=1;   //设一号点是黑色，与它相邻的都染成白色
    dfs(1,1); //从1号点开始
    return flag;
}

bool find(int i) //寻找增广路径
{
    int j;
    for(j=1;j<=n;j++)
    {
        if(g[i][j] && !visit[j])
        {
            visit[j]=true;
            if(link[j]==0 || find(link[j]))
            {
                link[j]=i;
                return true;
            }
        }
    }
    return false;
}

int main()
{
    int i,j,res;
    while(cin>>n>>k)
    {
        memset(g,0,sizeof(g));
        memset(link,0,sizeof(link));
        res=0;
        while(k--)
        {
            cin>>i>>j;
            g[i][j]=g[j][i]=true;
        }
        if(!check())
        {
            cout<<"No\n";
            continue;
        }
        //求最大匹配哦
        for(i=1;i<=n;i++) //以x集合为准找了一遍，又以y集合为准找了一遍，匹配数量增倍。[x]+[y]=n
        {
            memset(visit,0,sizeof(visit));
            if(find(i))
                res++;
        }
        cout<<res/2<<endl;
    }
    return 0;
}