月老的難題

時間限制：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月老的难题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。