nyoj——239
月老准备给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 来源 经典题目 上传者张云聪
二分最大匹配_匈牙利算法，用查询增广路线的方法实现
//匈牙利算法模板：注意用邻接矩阵可能会超时，建议用邻接表实现
bool find(int x){ int i,j; for (j=1;j<=m;j++){ //m表示集合_2的人数 //扫描每个妹子 if (line[x][j]==true && used[j]==false) //如果有暧昧并且还没有标记过(这里标记的意思是这次查找曾试图改变过该妹子的归属问题，但是没有成功，所以就不用瞎费工夫了） { used[j]=1; if (girl[j]==0 || find(girl[j])) { //名花无主或者能腾出个位置来，这里使用递归 girl[j]=x; return true; } } } return false; } //main() for (i=1;i<=n;i++)//n表示集合_1的人数 { memset(used,0,sizeof(used)); //这个在每一步中清空 if find(i) all+=1; }给你n个男生n个女生；把他们之间的关系给出来，问你最多可以组成多少对。
//普通结构体+加匈牙利算法（有点难理解）时间复杂度低
// 普通结构体的做法，邻接表比这种写法耗时间 #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAXN 501 #define N 10001 int head[N]; struct EDGE { int to,next; }edge[N]; int m=0; int visBoy[MAXN]; int visGirl[MAXN]; void add_edge(int u,int v) { edge[m].to=v; edge[m].next=head[u]; head[u]=m++; } int dfs(int boy) { int girl; int i; for(i=head[boy];i!=-1;i=edge[i].next) { girl=edge[i].to; if(!visBoy[girl]) { visBoy[girl]=1; if(!visGirl[girl]||dfs(visGirl[girl])) { visGirl[girl]=boy;//存的是与她配对的男生的编号. return 1; } } } return 0; } int main() { int t; scanf("%d",&t); while(t--) { memset(head,-1,sizeof(head)); memset(visGirl,0,sizeof(visGirl)); m=0;//极其关键,相当于初始化edge[N]; int n,k; scanf("%d%d",&n,&k); int i; for(i=0;i<k;i++) { int boy,girl; scanf("%d%d",&boy,&girl); add_edge(boy,girl); } int counter=0; for(i=1;i<=n;i++) { memset(visBoy,0,sizeof(visBoy)); if(dfs(i)) counter++; } printf("%d\n",counter); } return 0; } //vector 的做法 #include<stdio.h> #include<vector> #include<string.h> using namespace std; vector<int>line[501]; int vis[501],match[501];//标记数组，最大匹配数组 int dfs_match(int var) { int i,opvar;//opvar记录另一个集合的点 for(i=0;i<line[var].size();i++) { opvar=line[var][i]; if(!vis[opvar]) { vis[opvar]=1;//标记这个女生出现过 if(!match[opvar]||dfs_match(match[opvar])) {//如果没有匹配，或是可以收到在另一个集合中没有匹配的点 match[opvar]=var; return 1; } } } return 0;//未找到返回增广路线失败 } int main() { int t,sp,ep,i,n,k,cnt; scanf("%d",&t); while(t--) { memset(match,0,sizeof(match)); scanf("%d%d",&n,&k); for(i=0;i<k;i++) { scanf("%d%d",&sp,&ep); line[sp].push_back(ep); } cnt=0; for(i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); if(dfs_match(i)) { cnt++; } } printf("%d\n",cnt); for(i=0;i<=n;i++) line[i].clear(); } } //邻接表+匈牙利算法dfs实现 #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为NULL memset(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; }