HDU 3605 盗用标题： 二分图的多重匹配

九野的博客，转载请注明出处：http://blog.csdn.net/acmmmm/article/details/12843889

题意：

n个人m个星球，下面 n*m 的矩阵

i行第j个 为1 表示 第i人能住在j星球 为0表示不能居住

最后一行m个表示该星球容量

问是不是所有人都能住在m个星球里

思路：

这个题最大流比较好想

二分图建图：

n个人建x集 ， 矩阵直接做映射边， m个星球因为非单一匹配，所以用栈

这里需要一个优化就是，如果第i人不能居住了 ， 直接跳出匹配算法，输出NO

#include<stdio.h>#include<string.h>#define M 11#define N 100001#define stack Stackint n,m;int stack[M][N], top[M], Maxpeo[M];int map[N][M];bool T[M];int dfs(int u){for(int i = 1; i <= m; i ++)if(map[u][i] && !T[i]){T[i] = true;if(top[i]<Maxpeo[i]){stack[i][top[i] ++ ] = u;return 1;}for(int j = 0; j<top[i] ;j++)if( dfs(stack[i][j]) ){stack[i][j] = u;return 1;}}return 0;}bool solve(){memset(top, 0, sizeof(top));for(int i = 1; i <= n; i++){memset(T, 0, sizeof(T));if(!dfs(i)) return false;}return true;}void Input(){for(int i = 1; i <= n; i++)for(int j = 1; j <= m; j++)scanf("%d",&map[i][j]);for(int i = 1; i <= m; i++)scanf("%d",&Maxpeo[i]);}int main(){while(~scanf("%d %d",&n,&m)){Input();if(solve())printf("YES\n");else   printf("NO\n");}return 0;}/*1 1112 21 01 01 1ans:YESNO*/