As a teacher of a kindergarten, you have many things to do during a day, one of which is to allot candies to all children in your class. Today you have N candies for the coming M children. Each child likes different candy, and as a teacher who know them well, you can describe how the child i likes the candy j with a number Aji (Aji = 2 if the child i likes the candy j, or else Aji = 1).
The child i feels happy while ( Cij = 1 if the child i get the candy j, or else Cij = 0). Now your task is to allot the candies in such a way that makes every child happy (of course except you, ^_^).
Input
The first line of the input contains a single integer T (1 <= T <= 10), representing the number of cases that follow.
The first line of each case consists of two integers N and M (1 <= N <= 100000, 1 <= M <= 10), which are the number of candies and the number of children.
There are N lines following, the ith line containing M integers: Ai1, Ai2, Ai3, ..., AiM (1 <= Aij <= 2)
The last line of the case consists of M integers: B1, B2, B3, ..., BM (0 <= Bi <= 1000000000).
Output
For each case, if there is a way to make all children happy, display the word “Yes”. Otherwise, display the word “No”.
Sample Input
2
4 3
1 2 1
2 1 1
1 1 2
1 2 2
3 2 2
1 1
1
2
Sample Output
Yes
No
網絡流，主要是建圖
分配的時候肯定會優先給每個孩子分配喜歡的糖果，所以先只考慮Aij=2的孩子和糖果(i,j)。
如果Ai,j=2，那麼把孩子i向糖果j連一條容量為1的邊，再建立源點S，向每個孩子連一條容量為Bi/2的邊（因為每個開心值為2的糖果只算1，所以孩子的B值也要先除以2），最後把每個糖果向匯點T連容量為1的邊，做一次網絡最大流。
假設S到孩子i的流量為fi，說明孩子i已經獲得了fi*2點快樂值，還需要Bi-fi*2點，這時候f1+f2+..+fm是總共分出去的糖果數，那麼還剩N-(f1+f2+..+fm)個糖果，如果這個數>=sigma(Bi-fi*2)，即剩余的糖果數大於等於孩子還需要的總共快樂值，則有解，否則無解
PS：每個孩子平均能吃10000個糖，我真是無限ORZ
以下使用的是劉汝佳白書上的DINIC算法模板做的
#include<iostream>
#include<algorithm>
#include<cstring>
#define size_num 100200
#include<vector>
#include<queue>
#define INF 1e8
using namespace std;
int child[105];
struct Dinic
{
struct Edge{int from,to,cap,flow;};
vector<Edge> edges;
//邊表。edges[e]和edges[e+1]互為反向弧,
//注意到e必須是偶數即是大的奇數與比他小的偶數互為反向邊，即e與e^1互為反向邊
vector<int> G[size_num];
//領接表，G[i][j]表示節點i的第j條邊在e數組中的序號
void add_edge(int from,int to,int cap)
{
edges.push_back((Edge){from,to,cap,0});//加入正向邊
edges.push_back((Edge){to,from,0,0});//加入反向邊
int m=edges.size();
G[from].push_back(m-2);//存的是邊的位子
G[to].push_back(m-1);//貌似有一種靜態鏈表的感覺
}
int s,t;//源點編號和匯點編號
bool vis[size_num];//bfs時使用
int d[size_num];//從起點到i的距離
int cur[size_num];//當前弧的下標
void init()
{
edges.clear();
for(int i=0;i<size_num;i++)
G[i].clear();
}
bool bfs()
{
memset(vis,0,sizeof(vis));
queue<int > q;
q.push(s);
d[s]=0;
vis[s]=1;
while(!q.empty())
{
int x=q.front();q.pop();
for(int i=0;i<G[x].size();i++)
{
Edge&e=edges[G[x][i]];
if(!vis[e.to]&&e.cap>e.flow)
{
vis[e.to]=1;
d[e.to]=d[x]+1;
q.push(e.to);
}
}
}
return vis[t];
}
//dfs
int dfs(int x,int a)
{
if (x==t||a==0) return a;
int flow=0,f;
for(int &i=cur[x];i<G[x].size();i++)//從上次考慮的弧
{
Edge &e=edges[G[x][i]];
if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow)))>0)
{
e.flow+=f;//增加正向的流量
edges[G[x][i]^1].flow-=f;//減少反向的流量
flow+=f;
a-=f;
if(a==0) break;
}
}
return flow;
}
//
int maxflow(int s,int t)
{
this->s=s;this->t=t;
int flow=0;
while(bfs())
{
memset(cur,0,sizeof(cur));
flow+=dfs(s,INF);
}
return flow;
}
}solve;
void read()
{
solve.init();
int n,m;//糖果數量和孩子的數量
cin>>n>>m;
int s=0,t=1+m+n;
//solve->n=t+1;
//1->m表示孩子，m+1->m+n表示糖果
for(int i=1;i<=n;i++)
{
solve.add_edge(i+m,t,1);
for(int j=1;j<=m;j++)
{
int temp;
cin>>temp;
if(temp==2)
solve.add_edge(j,m+i,1);
}
}
long long sum=0;
for(int i=1;i<=m;i++)
{
cin>>child[i];
sum+=child[i];
solve.add_edge(s,i,child[i]/2);
}
int f=solve.maxflow(s,t);
int yu=n-f;
if(sum<=yu+f*2)
cout<<"Yes\n";
else
cout<<"No\n";
}
int main()
{
int T;cin>>T;
while(T--)
read();
return 0;
}
