首页 > 其他 > 详细

POJ1274-The Perfect Stall

时间:2019-11-12 18:54:41      阅读:79      评论:0      收藏:0      [点我收藏+]

啊就是一道匈牙利裸题,然而谁能想到我因为scanf在这题上wa了n次呢(我真是。。)

#include<cstdio>
#include<cstring>
#define maxn 205
#define maxm 40005
using namespace std;
int num,last[maxn],to[maxm],nxt[maxm],n,m,used[maxn],match[maxn],cnt;
int dfs(int x)
{
    for (int i=last[x];i;i=nxt[i])
    {
        if (!used[to[i]])
        {
            used[to[i]]=1;
            if (!match[to[i]] || dfs(match[to[i]]))
            {
                match[to[i]]=x;
                return 1;
             }
         }
    }
    return 0;
}
void add(int x,int y)
{
    to[++num]=y;nxt[num]=last[x];last[x]=num;
}
int main()
{
    int i,a,x;
    while (scanf("%d%d",&n,&m)!=EOF)
    {
        memset(last,0,sizeof(last));
        memset(nxt,0,sizeof(nxt));
        memset(to,0,sizeof(to));
        memset(match,0,sizeof(match));
        cnt=0;num=0;
        for (i=1;i<=n;i++)
        {
            scanf("%d",&a);
            while (a--)
            {
                scanf("%d",&x);
                add(i,x);
            }
        }
        for (i=1;i<=n;i++)
        {
            memset(used,0,sizeof(used));
            cnt+=dfs(i);
        }
        printf("%d\n",cnt);
    }
    return 0;
}

 

POJ1274-The Perfect Stall

原文:https://www.cnblogs.com/lsykk/p/11844245.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!