1068.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 44 行

#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
int a[1250][1250],b[1250],c[1250];
bool sign[1250];
int len;
int get(int u){
    int v;
    for(v=0;v<len;v++){
        if(a[u][v]==1&&sign[v]==false){
            sign[v]=true;
            if(c[v]==-1||get(c[v])==1){
                b[u]=v;c[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
void main()
{
    int i,p,q,n,rst;
    while(scanf("%d",&len)==1){
        memset(a,0,sizeof(a));
        memset(b,-1,sizeof(b));
        memset(c,-1,sizeof(c));
        for(i=0;i<len;i++){
			scanf("%d: (%d)",&p,&n);
			while(n--){
				scanf("%d",&q);
				a[p][q]=1;
				a[q][p]=1;
			}
        }
        rst=0;
        for(p=0;p<len;p++){
            memset(sign,0,sizeof(sign));
            rst+=get(p);
        }
        cout<<len-rst/2<<endl;
    }
}