题目链接:点击打开链接
题目很简单,不在作解释。
分别用二维数组和vector实现了一下。直接代码:
二维数组:
#include <cstdio> #include <cstring> #include <algorithm> #define CLR(arr,val) memset(arr,val,sizeof(arr)) using namespace std; const int N=203; int n,m,Match[N]; bool vis[N],map[N][N]; bool Find_Path(int x){ for(int i=1;i<=m;i++){ if(map[x][i]&&!vis[i]){ vis[i]=true; if(!Match[i]||Find_Path(Match[i])){ Match[i]=x; return true; } } } return false; } int main(){ while(~scanf("%d%d",&n,&m)){ CLR(Match,0);CLR(vis,0);CLR(map,0); for(int i=1;i<=n;i++){ int number; scanf("%d",&number); for(int j=1;j<=number;j++){ int tmp; scanf("%d",&tmp); map[i][tmp]=true; } } int ans=0; for(int i=1;i<=n;i++){ if(Find_Path(i)) ans++; CLR(vis,0); } printf("%d\n",ans); } return 0; }
vector实现:
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #define CLR(arr,val) memset(arr,val,sizeof(arr)) using namespace std; const int N=203; int match[N],n,m; vector<int> map[N]; bool vis[N]; bool Find_Path(int x){ for(unsigned int i=0;i<map[x].size();i++){ if(!vis[map[x][i]]){ vis[map[x][i]]=true; if(!match[map[x][i]]||Find_Path(match[map[x][i]])){ match[map[x][i]]=x; return true; } } } return false; } int main(){ while(~scanf("%d%d",&n,&m)){ CLR(map,0);CLR(match,0);CLR(vis,0); for(int i=1;i<=n;i++){ int number; scanf("%d",&number); for(int j=1;j<=number;j++){ int m; scanf("%d",&m); map[i].push_back(m); } } int ans=0; for(int i=1;i<=n;i++){ if(Find_Path(i)) ans++; CLR(vis,0); } printf("%d\n",ans); } return 0; }
不能一直这么弄了,我需要学习一些新的东西。
I Need Someting New.