本文主要是介绍http://poj.org/problem?id=1274The Perfect Stall,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
此题是二分图最大匹配模板题,,,,杯具的是匈牙利算法我竟然写错两个地方,,这一题简单题意不解释。。。
#include<iostream>
#include<string.h>
#define N 201
#include<vector>
using namespace std;
bool visit[N];
int match[N] ;
int n,m;
vector<int>map[N];
bool dfs(int x)
{ for(int i=0;i<map[x].size();++i)if(!visit[map[x][i]]){ visit[map[x][i]]=true;if(match[map[x][i]]==-1||dfs(match[map[x][i]])){match[map[x][i]]=x;return true;}}return false;
}
int main()
{ while(cin>>n>>m){ memset(match,-1,sizeof(match));for(int i=0;i<=n;++i)map[i].clear();for(int i=1;i<=n;++i){ int s;cin>>s;for(int j=0;j<s;++j){ int a;cin>>a;map[i].push_back(a);}}int ans=0;for(int i=1;i<=n;++i){ memset(visit,false,sizeof(visit));if(dfs(i)) ans++;}cout<<ans<<endl;}return 0;}
这篇关于http://poj.org/problem?id=1274The Perfect Stall的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!