学步园

大意不再赘述。

思路：用网络流写的时候，TLE了，于是改用二分多重匹配写写，等下去想想用网络流建图。

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
using namespace std;

const int MAXN = 100010; //最大顶点数 

bool G[MAXN][12];
bool vis[15]; //寻找增广路径时的标记数组 
int nx, ny;

int vylink[MAXN]; //表示右集合i顶点匹配到左集合的顶点数目 
int ylink[12][MAXN]; //表示与右集合i顶点匹配的第j个元素 
int limit[12]; //表示右集合最多匹配顶点的个数 

void init()
{
	memset(G, 0, sizeof(G));
}

bool find(int u)
{
	for(int i = 0; i < ny; i++) if(G[u][i] && !vis[i])
	{
		vis[i] = 1;
		if(vylink[i] < limit[i])
		{
			ylink[i][vylink[i]++] = u;
			return 1;
		}
		for(int j = 0; j < vylink[i]; j++)
		{
			if(find(ylink[i][j]))
			{
				ylink[i][j] = u;
				return 1;
			}
		}
	}
	return 0;
}

bool MulMatch()
{
	memset(vylink, 0, sizeof(vylink));
	for(int i = 0; i < nx; i++)
	{
		memset(vis, 0, sizeof(vis));
		if(!find(i)) return 0;
	}
	return 1;
}

void build()
{
	init();
	for(int i = 0; i < nx; i++)
	{
		for(int j = 0; j < ny; j++)
		{
			scanf("%d", &G[i][j]);
		}
	}
}

void solve()
{
	build();
	for(int i = 0; i < ny; i++) scanf("%d", &limit[i]);
	if(MulMatch()) printf("YES\n");
	else printf("NO\n");
}

int main()
{
	while(~scanf("%d%d", &nx, &ny))
	{
		solve();
	}
	return 0;
}