二分图婚配

二分图匹配

二分图匹配可用匈牙利算法，离散中学过，就是找一条交替链，让路径的起点和终点都是还没有匹配过的点，路径经过的连线是一条没被匹配、一条已经匹配过，再下一条又没匹配这样交替地出现，显然路径里没被匹配的连线比已经匹配了的连线多一条，于是修改匹配图，把路径里所有匹配过的连线去掉匹配关系，把没有匹配的连线变成匹配的，这样匹配数就比原来多1个。不断执行上述操作，直到找不到这样的路径为止。

POJ-1274-The Perfect Stall

http://poj.org/problem?id=1274

基本的二分图匹配，套模版即可

#include<stdio.h>#include<string.h>#include<stdlib.h>int n,m;int map[205][205];int state[205]; //记录每个点是否被搜索过 int result[205]; //记录匹配点的编号 int find(int a){int i;for(i=1;i<=m;i++)if(!state[i]&&map[a][i]) //如果节点i与a相邻并且未被查找过{state[i]=1; //标记i为已查找过if(result[i]==0||find(result[i])) //如果i未在前一个匹配M中 || i在匹配M中，但是从与i相邻的节点出发可以有增广路 {result[i]=a; //记录查找成功记录 return 1;}}return 0;}int main(){int i,t,temp,ans;while(scanf("%d%d",&n,&m)!=EOF){ memset(map,0,sizeof(map));for(i=1;i<=n;i++) //建图{ scanf("%d",&t); while(t--) { scanf("%d",&temp); map[i][temp]=1; }}ans=0;memset(result,0,sizeof(result));for(i=1;i<=n;i++){memset(state,0,sizeof(state)); //清空上次搜索时的标记 if(find(i)) //从节点i尝试扩展ans++;}printf("%d\n",ans);}return 0;}