#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define c(a) memset(a,0l,sizeof a)
#define M 1510
typedef struct abcd{short to;abcd*next;} abcd;abcd*head[M];
void add(short x,short y){abcd*temp=(abcd*)malloc(sizeof (abcd));temp->to=y;temp->next=head[x];head[x]=temp;}
short fa[M],a[M];
short ans;
bool state[M];
short result[M];
short n,m;
void del(abcd*temp){
if(!temp||!temp->next)return ;
del(temp->next);
free(temp->next);}
void initialize(){c(fa);c(a);ans=0;c(result);for(short i=1;i<M;i++)del(head[i]);c(head);}
int find(short x)
{
    short p;
    if(fa[x]==x||!fa[x])return fa[x]=x;
    p=fa[x];
    fa[x]=find(fa[x]);
    a[x]=(a[x]+a[p])%2;
    return fa[x];
}
bool hungary(short x)
{
    abcd*temp;
    for(temp=head[x];temp;temp=temp->next)if(!state[temp->to])
    {
        state[temp->to]=1;
        if(!result[temp->to]||hungary(result[temp->to]))
        {
            result[temp->to]=x;
            return true;
        }
    }
    return false;
}

int main()
{
    short i,j,x,y,fx,fy;
    while(~scanf("%d",&n))
    {
        initialize();
        for(i=1;i<=n;i++)
        {
            scanf("%hi:(%hi)",&x,&m);x++;
            for(j=1;j<=m;j++)
            {
            	scanf("%hi",&y);y++;
        	    fx=find(x);fy=find(y);
        	    if(fx!=fy)fa[fx]=fy,a[fx]=!(a[x]^a[y]);
        	    add(x,y);add(y,x);
			}
        }
        for(i=1;i<=n;i++)
        {
            find(i);
            if(a[i])continue;
            c(state);
            if(hungary(i))ans++;
        }
        printf("%d\n",ans);
    }
}

其实a数组应该开成bool。。不管了

• Re:二分图可以过。int全都开成short，不能用链式前向星，要用链表，而且要free掉，9868KB险过 (10) shiaaaa 2017-07-04 15:32:58
  • Re:二分图可以过。int全都开成short，不能用链式前向星，要用链表，而且要free掉，9868KB险过 (14) 1520182523 2019-08-18 09:55:22