题目网站：
资料网址： （大神的二分题......Orz）
二分图——二分匹配之匈牙利算法
模板：
int g[MAXN][MAXN];int uN,vN;int linker[MAXN];bool used[MAXN];bool dfs(int u){ int v; for(v=1;v<=vN;v++) //右子集 if(g[u][v]&&!used[v]) //左子集和右子集中的u,v有关系，并且右子集的这个元素未被访问 { used[v]=true; //标记 if(linker[v]==-1||dfs(linker[v])) //右子集的这个元素还没有被配对，或者能配对 { linker[v]=u; //与v配对的是u return true; } } return false; } int hungary(){ int res=0,u; memset(linker,-1,sizeof(linker)); for(u=1;u<=uN;u++) //左子集 { memset(used,0,sizeof(used)); if(dfs(u)) res++; //最大匹配的个数 } return res; } 用匈牙利算法可解决A,B,C
A
题意：有n种课,m个学生，每种课有几个学生参加，每个学生可以代表一种课，问是否每种课都有学生代表？ ————即问最大匹配关系是否=课程的种类
1 #include2 #include 3 #include 4 using namespace std; 5 int n,m; 6 int map[102][302],vist[302],c[302]; 7 int dfs(int k) 8 { 9 for(int i=1;i<=m;i++)10 if(map[k][i] && !vist[i])11 {12 vist[i]=1;13 if(c[i]==0 || dfs(c[i]))14 {15 c[i]=k;16 return 1;17 }18 }19 return 0;20 }21 int main()22 {23 int T;24 scanf("%d",&T);25 while(T--)26 {27 scanf("%d%d",&n,&m); //n种课28 memset(map,0,sizeof(map));29 memset(c,0,sizeof(c));30 int i,sum=0,a,b,j;31 for(i=1;i<=n;i++) //课的编号32 {33 scanf("%d",&b);34 for(j=1;j<=b;j++)35 {36 scanf("%d",&a); //学生的编号37 map[i][a]=1; //有关系38 }39 }40 for(i=1;i<=n;i++)41 {42 memset(vist,0,sizeof(vist));43 if(dfs(i))44 sum++;45 }46 if(sum==n)47 printf("YES\n");48 else49 printf("NO\n");50 }51 }
B 题意：能否把对角线上都变成1？只能交换行或者列 ————即匈牙利算法判断能否达成，并记录过程
#include#include #include #include using namespace std;int n,m;int map[102][102],vist[102],c[102],a[102],b[102];int dfs(int k){ for(int i=1;i<=n;i++) if(map[k][i] && !vist[i]) { vist[i]=1; if(c[i]==0 || dfs(c[i])) { c[i]=k; return 1; } } return 0;}int main(){ while(~scanf("%d",&n)) { memset(map,0,sizeof(map)); memset(c,0,sizeof(c)); int i,sum=0,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) scanf("%d",&map[i][j]); for(i=1;i<=n;i++) { memset(vist,0,sizeof(vist)); if(dfs(i)) sum++; } if(sum
C 匈牙利算法的运用 题意：求最大匹配 不解释
1 #include2 #include 3 #include 4 using namespace std; 5 int n,m; 6 int map[502][502],vist[502],c[502]; 7 int dfs(int k) 8 { 9 for(int i=1;i<=n;i++)10 if(map[k][i] && !vist[i])11 {12 vist[i]=1;13 if(c[i]==0 || dfs(c[i]))14 {15 c[i]=k;16 return 1;17 }18 }19 return 0;20 }21 int main()22 {23 while(~scanf("%d%d",&n,&m))24 {25 memset(map,0,sizeof(map));26 memset(c,0,sizeof(c));27 int i,x,y,sum=0;28 for(i=1;i<=m;i++)29 {30 scanf("%d%d",&x,&y);31 map[x][y]=1;32 }33 for(i=1;i<=n;i++)34 {35 memset(vist,0,sizeof(vist));36 if(dfs(i))37 sum++;38 }39 printf("%d\n",sum);40 }41 }