// 模板。(匈牙利的稍微改写)
// 例题 :hdu 3605
// 题意:有n(n <= 100000)个人和m(m <= 10)个星球, 每个人有自己想去的星球(不止一个), 但每个星球能承受的人数不同。问: 能不能把所有人安排到他自己想去的星球上;
// 输入(机翻):
//输出 YES or NO
1 #include<iostream> 2 #define read(n) n = read_n() 3 #define rep(i, n) for(int i=0;i!=n;++i) 4 #define rep1(i, n) for(int i=1;i<=n;++i) 5 using namespace std; 6 7 inline int read_n() { 8 char c=getchar();int x=0,f=1; 9 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 10 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 11 return x*f; 12 } 13 // ----------------------------------------------------- 14 const int MAXN = 100000+5; 15 const int MAXM = 10+5; 16 const int MAXE = MAXN*MAXM; 17 18 int num; 19 int head[MAXN]; 20 struct node { 21 int v, next; 22 } edge[MAXE]; 23 24 inline void add(int x, int y) { 25 edge[num].v = y; 26 edge[num].next = head[x]; 27 head[x] = num++; 28 } 29 30 int n, m; 31 int maxn[MAXM]; 32 33 int cnt[MAXM]; 34 int love[MAXM][MAXN]; 35 bool vis[MAXM]; 36 // -----------------核心---------------------- 37 bool dfs(int u) { 38 for(int i = head[u]; i != -1; i = edge[i].next) { 39 int v = edge[i].v; 40 if(!vis[v]) { 41 vis[v] = true; 42 if(cnt[v] < maxn[v]) {// 如果v还有"位置"匹配 43 love[v][++cnt[v]] = u; 44 return true; 45 } 46 for(int j = 1; j <= cnt[v]; ++j) {// 若没有位置了, 从已经匹配的上面找是否有人能腾出位置 47 if(dfs(love[v][j])) { 48 love[v][j] = u; 49 return true; 50 } 51 } 52 } 53 } 54 return false; 55 } 56 // --------------------------------------------- 57 bool solve() { 58 rep1(i, m) cnt[i] = 0; 59 rep1(i, n) { 60 rep1(j, m) vis[j] = false; 61 if(!dfs(i)) return false; 62 } 63 return true; 64 } 65 66 int main() { 67 while(cin >> n >> m) { 68 num = 0; 69 rep1(i, n) head[i] = -1; 70 int x; 71 rep1(i, n) rep1(j, m) { 72 read(x); 73 if(x == 1) add(i, j); 74 } 75 rep1(i, m) read(maxn[i]); 76 if(solve()) cout << "YES\n"; 77 else cout << "NO\n"; 78 } 79 return 0; 80 }