`
thecloud
  • 浏览: 871903 次
文章分类
社区版块
存档分类
最新评论

hdu 1068 Girls and Boys 二分匹配

 
阅读更多

很标准的二分匹配,用的是匈牙利算法。

#include<iostream>
#include<string>

using namespace std;

int key[1000][1000],total,count;   //count是所有点能找到增广路径的    total是总人数

int ok[1000];      //记录右边所有的已经匹配的点,ok[i]=j右边第i个与左边第j个匹配
int rightt[1000];    //记录在一次递归中,右边各点是否已经匹配

int route(int );

int main()
{
    int a,b,c;
    string no;
    char m;

    while(cin>>total)
    {
        count=0;

        memset(key,0,sizeof(key));

        for(int i=0;i<total;i++)
        {
            cin>>a>>m>>m>>b>>m;

            for(int j=0;j<b;j++)
            {
                scanf("%d",&c);
                key[a][c]=1;
            }
        }
        memset(ok,-1,sizeof(ok));

        for(i=0;i<total;i++)          //每个点为起点,都找一次增广路径
        {
            memset(rightt,0,sizeof(rightt));

            if(route(i))
                count++;
        }

        cout<<total-count/2<<endl;
    }

    return 0;
}

int route(int i)
{
    for(int j=0;j<total;j++)
    {
        if(key[i][j]&&!rightt[j])       //j点在这次递归中,没有被访问过
        {
            rightt[j]=1;
            if(ok[j]==-1||route(ok[j]))
            {
                ok[j]=i;
                return 1;
            }
        }
    }
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics