for span font 哪些 eof 准备 pac sizeof
时间限制:1000 ms | 内存限制:65535 KB
难度:4
描述
月老准备给 n 个女孩与 n 个男孩牵红线,成就一对对美好的姻缘。
现在,由于一些原因,部分男孩与女孩可能结成幸福的一家,部分可能不会结成幸福的家庭。
现在已知哪些男孩与哪些女孩如果结婚的话,可以结成幸福的家庭,月老准备促成尽可能多的幸福家庭,请你帮他找出最多可能促成的幸福家庭数量吧。
假设男孩们分别编号为 1~n, 女孩们也分别编号为 1~n。
输入
第一行是一个整数 T, 表示测试数据的组数 (1<=T<=400) 每组测试数据的第一行有两个整数 n,K,其中男孩的人数与女孩的人数都是 n。(n<=500,K<=10 000)随后的 K 行,每行有两个整数 i,j 表示第 i 个男孩与第 j 个女孩有可能结成幸福的家庭。(1<=i,j<=n)
输出
对每组测试数据,输出最多可能促成的幸福家庭数量
样例输入
1
3 4
1 1
1 3
2 2
3 2
样例输出
2
- /*
- 月老准备给n个女孩与n个男孩牵红线,成就一对对美好的姻缘。
- 现在,由于一些原因,部分男孩与女孩可能结成幸福的一家,部分可能不会结成幸福的家庭。
- 现在已知哪些男孩与哪些女孩如果结婚的话,可以结成幸福的家庭,月老准备促成尽可能多的幸福家庭,
- 请你帮他找出最多可能促成的幸福家庭数量吧。
- */
- #include <stdio.h>
- #include <vector>
- #include <cstring>
- using namespace std;
- vector<int> v[505];
- int vis[505],link[505];
- bool getnum(int i)
- {
- for(int j=0;j<v[i].size();j++)
- {
- if(vis[v[i][j]]==0) //注意这里容器的访问,ij表示v[i]中的第j个元素是
- {
- vis[v[i][j]]=1;
- if(link[v[i][j]]==0 || getnum(link[v[i][j]]))
- {
- link[v[i][j]]=i;
- return true;
- }
- //vis[v[i][j]]=0;//这里不要这个因为这个会重复判断
- }
- }
- return false;
- }
- int main()
- {
- int T,n,k,a,b,count;
- scanf("%d",&T);
- while(T--)
- {
- scanf("%d%d",&n,&k);
- memset(v,0,sizeof(v));
- memset(link,0,sizeof(link));
- for(int i=0;i<k;i++)
- {
- scanf("%d%d",&a,&b);
- v[a].push_back(b);
- }
- count=0;
- for(int i=1;i<=n;i++)
- {
- memset(vis,0,sizeof(vis));//清零
- if(getnum(i))
- count++;
- }
- printf("%d\n",count);
- }
- }
nyoj 239 月老的难题
来源: http://www.bubuko.com/infodetail-2128960.html