PKU 1274-The Perfect Stall

問題概要

牛に部屋を与えたいが、牛はそれぞれ部屋の希望をいくつかもっており、さらに一つの部屋に一つの牛しか割り当てられない。希望の部屋に割り当てられる牛の数を求めよ。

解法

二部グラフの最大マッチング

実装(C++)

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;


typedef vector<int> Edges;
typedef vector<Edges> Graph;
bool dfs(const Graph &G,int v,vector<int> &match,vector<bool> &used){
        if(v<0)return true;
        for(int i=0;i<(int)G[v].size();i++){
                int src=v,dst=G[v][i];
                if(used[dst])continue;
                used[dst]=true;
                if(dfs(G,match[dst],match,used)){
                        match[src]=dst;
                        match[dst]=src;
                        return true;
                }
        }
        return false;
}
int bipartite_matching(const Graph &G,int L){
        int res=0;
        vector<int> match(G.size(),-1);
        for(int i=0;i<L;i++){
                vector<bool> used(G.size(),false);
                if(dfs(G,i,match,used))res++;
        }
        return res;
}
int main(){
        int N,M;
        while(~scanf("%d%d",&N,&M)){
                Graph G(N+M);
                for(int i=0;i<N;i++){
                        int k;
                        scanf("%d",&k);
                        for(;k--;){
                                int t;
                                scanf("%d",&t);
                                G[i].push_back(N+t-1);
                                G[N+t-1].push_back(i);
                        }
                }
                printf("%d\n",bipartite_matching(G,N));
        }
}