YAIMH1993的笔记
如果奇迹木有出现,就去创造一个
posts - 29,comments - 0,trackbacks - 0
#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 1555 , maxm = 3333;
int linky[maxn],visy[maxn];
vector<int> G[maxn];
int n;
bool find(int u) {
    int sz = G[u].size();
    for(int i=0;i<sz;i++) {
        int v = G[u][i];
        if(visy[v]) continue;
        visy[v] = 1;
        if(linky[v] == -1 || find( linky[v] )) {
            linky[v] = u;
            return 1;   
        }   
    }
    return 0;   
}
int ans;
void solve() {
    ans = 0;
    memset(linky,-1,sizeof(int)*n);
    for(int i=0;i<n;i++) {
        memset(visy,0,sizeof(visy));
        if(find(i)) ans ++;
    }   
}
int main() {
    while(~scanf("%d",&n)) {
        for(int i=0;i<n;i++) G[i].clear();
        int u,num,v;
        for(int i=0;i<n;i++) {
            scanf("%d:(%d)",&u,&num);
            while(num--) {
                scanf("%d",&v);
                G[u].push_back(v);
                G[v].push_back(u);   
            }   
        }   
        solve();
        printf("%d\n",ans/2);
    }
    return 0;   
}
posted on 2012-10-08 23:45 YouAreInMyHeart 阅读(127) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理