学步园

一个裸的二分图最大匹配。这两天看了下匹配，以前一直以为很难，看了看，发现不是很难，很多题难的地方在于建图。要多做题，多学学不同的建图方式。#include <stdio.h><br /> #include <string.h><br /> #define N 305<br /> int map[N][90],pre[N];<br /> bool used[N];<br /> int n,m=85;<br /> bool dfs(int u)<br /> {<br /> int i;<br /> for(i=1;i<=m;i++)<br /> {<br /> if(!used[i]&&map[u][i])<br /> {<br /> used[i]=1;<br /> if(pre[i]==-1||dfs(pre[i]))<br /> {<br /> pre[i]=u;<br /> return true;<br /> }<br /> }<br /> }<br /> return false;<br /> }<br /> int main()<br /> {<br /> while(scanf("%d",&n)==1)<br /> {<br /> int i;<br /> memset(map,0,sizeof(map));<br /> memset(pre,-1,sizeof(pre));<br /> for(i=1;i<=n;i++)<br /> {<br /> int t,a,b;<br /> scanf("%d",&t);<br /> while(t--)<br /> {<br /> scanf("%d%d",&a,&b);<br /> map[i][(a-1)*12+b]=1;<br /> }<br /> }<br /> int ans=0;<br /> for(i=1;i<=n;i++)<br /> {<br /> memset(used,0,sizeof(used));<br /> if(dfs(i))<br /> ans++;<br /> }<br /> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }