nyoj239月老的难题

月老的难题

时间限制：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

此篇只是纯属的记录：
看别人的文章学习http://blog.csdn.net/dark_scope/article/details/8880547

AC代码：
//邻接表+匈牙利算法bfs实现 #include <stdio.h> #include <string.h> #include <stdlib.h>const int max_n = 505; int link[max_n]; char used[max_n]; struct Node{int to;Node *next; }G[max_n];int dfs(int i) {for(Node *j = G[i].next; j != NULL; j=j->next) {int to = j->to;if(used[to] == 0) {used[to] = 1;if(link[to] == 0 || dfs(link[to])) {//没有被配对||别人腾出 link[to] = i;return 1;}}}return 0; }int count(int n) {int ans = 0, i = 1;for(; i <= n; i++) {memset(used, 0, sizeof(used));//特别注意 if(dfs(i)) ans++;}return ans; }void add(int x, int y) {Node *np = NULL, *gp = &G[x];char flag = 1;np = (Node *)malloc(sizeof(Node));if(np == NULL) ;//平时要有while(gp->next != NULL) {if(gp->to == y) {//因为要去重，所以干脆用尾插法flag = 0;break;}gp = gp->next;}if(flag) {np->to = y;np->next = NULL;gp->next = np;} }int main() {int t, n, k, i;scanf("%d", &t);while(t--) {int x, y;scanf("%d%d", &n, &k);memset(G, 0, sizeof(Node)*(n+1));//主要是初始化next为NULLmemset(link, 0, sizeof(link));for(i = 0; i < k; i++) {scanf("%d%d", &x, &y);add(x,y);}printf("%d\n", count(n));}return 0; }

总结

以上是生活随笔为你收集整理的nyoj239月老的难题的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。