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)); } }