随笔-141  评论-9  文章-3  trackbacks-0
USACO 4.2.2 The Perfect Stall(二分图最大匹配, 匈牙利算法)

 

/*
ID: lorelei3
TASK: stall4
LANG: C++
*/

#include <fstream>
#include <memory.h>

using namespace std;

const int MAXN = 205;

int a[MAXN][MAXN], match[MAXN];
int n,m, ans;
bool visited[MAXN];

bool dfs(int k){
    for(int i=1; i<=a[k][0]; ++i){
        int v = a[k][i];
        if(!visited[v]){
            visited[v]=true;
            if(!match[v] || dfs(match[v])){
                match[v] = k;
                return true;
            }
        }
    }
    return false;
}

void search(){
    for(int i=1; i<=n; ++i){
        memset(visited, 0, sizeof(visited));
        if(dfs(i))
            ans++;
    }
}

int main(){

    ifstream fin("stall4.in");
    ofstream fout("stall4.out");

    fin>>n>>m;

    for(int i=1; i<=n; ++i){
        fin>>a[i][0];
        for(int j=1; j<=a[i][0]; ++j){
            fin>>a[i][j];
        }
    }

    search();

    fout<<ans<<endl;

    return 0;
}
posted on 2011-01-25 10:48 小阮 阅读(402) 评论(0)  编辑 收藏 引用 所属分类: USACO

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


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮