题意：给N个孩子分配M个糖果。
有一个N*M的矩阵表示孩子和糖果的关系，若第i行第j列的数是1则表示第i个孩子喜欢第j个糖果，反之不喜欢。
已知，若一个孩子被分配到他喜欢的糖果那么他将获得K的快乐值，反之只能获取1的快乐值。
现在给你这N个孩子需要满足的快乐值，问你能不能满足所有孩子的需求。
1<=N<=13, 1<=M<=13, 2<=K<=10
0<=B[i]<=1000
思路：RYZ作业
费用流（经典？）模型之一
这题的建模是使用最大费用最大流将各人喜欢的糖果作用最大化
From：http://blog.csdn.net/chenzhenyu123456/article/details/48130365
建图：设置超级源点source，超级汇点sink，用a表示当前孩子需要满足的快乐值
1，source向每个糖果建边，容量1，费用0；
2，只考虑有特殊的糖，那么对于第i个人喜欢j糖果，则j糖果向第i个人建边，容量为1，费用为0；
3，每个孩子向汇点建边。这时需要分类讨论
(1) a % K == 0，表示该孩子选择(a / K)个他喜欢的糖果就可以满足，而且该孩子选择1个他喜欢的糖果，会获取K的快乐值。 建边信息——容量为(a / K)，费用为K；
(2) a % K != 0，表示该孩子选择(a / K + 1)个他喜欢的糖果才能满足，这时我们不能只建一条容量为(a / K + 1)，费用为K的边，如果这样处理我们就放大了最大流时费用的最大效益。
因此我们要建一条容量为(a / K)，费用为K的边，再建一条容量为1，费用为a % K的边。这样的话在用特殊糖果满足该孩子的需求时，才不会使最后流入汇点的费用增加
建好图，跑一次最大费用最大流。
最终结果：（用sumflow记录所有孩子需要满足的快乐值之和）
最大费用cost——特殊的糖被充分利用后所分配的快乐值之和。若cost >= sumflow 则表示已经满足条件。
最大流flow——为了达到这样的程度使用的糖的数量。
这样就还剩M - flow数目的糖被我们当做普通的糖使用，只要M - flow >= sumflow - cost，就可以满足条件。
1 var head,vet,next,len1,len2,fan,dis:array[1..2000]of longint; 2 inq:array[1..2000]of boolean; 3 q,b:array[0..2000]of longint; 4 a:array[1..20,1..20]of longint; 5 pre:array[1..2000,1..2]of longint; 6 n,m,sum,ans1,ans2,tot,source,src,s,cas,v,i,j,k:longint; 7 8 procedure add(a,b,c,d:longint); 9 begin 10 inc(tot); 11 next[tot]:=head[a]; 12 vet[tot]:=b; 13 len1[tot]:=c; 14 len2[tot]:=d; 15 head[a]:=tot; 16 17 inc(tot); 18 next[tot]:=head[b]; 19 vet[tot]:=a; 20 len1[tot]:=0; 21 len2[tot]:=-d; 22 head[b]:=tot; 23 end; 24 25 function min(x,y:longint):longint; 26 begin 27 if x<y then exit(x); 28 exit(y); 29 end; 30 31 function spfa:boolean; 32 var u,e,v,t,w,i:longint; 33 begin 34 for i:=1 to s do 35 begin 36 dis[i]:=-(maxlongint>>1); 37 inq[i]:=false; 38 end; 39 t:=0; w:=1; q[1]:=source; dis[source]:=0; inq[source]:=true; 40 while t<w do 41 begin 42 inc(t); u:=q[t mod 100]; inq[u]:=false; 43 e:=head[u]; 44 while e<>0 do 45 begin 46 v:=vet[e]; 47 if (len1[e]>0)and(dis[u]+len2[e]>dis[v]) then 48 begin 49 dis[v]:=dis[u]+len2[e]; 50 pre[v,1]:=u; 51 pre[v,2]:=e; 52 if not inq[v] then 53 begin 54 inc(w); q[w mod 100]:=v; inq[v]:=true; 55 end; 56 end; 57 e:=next[e]; 58 end; 59 end; 60 if dis[src]=-(maxlongint>>1) then exit(false); 61 exit(true); 62 end; 63 64 procedure mcf; 65 var k,e,t:longint; 66 begin 67 k:=src; t:=maxlongint; 68 while k<>source do 69 begin 70 t:=min(t,len1[pre[k,2]]); 71 k:=pre[k,1]; 72 end; 73 k:=src; 74 while k<>source do 75 begin 76 e:=pre[k,2]; 77 len1[e]:=len1[e]-t; 78 len1[fan[e]]:=len1[fan[e]]+t; 79 ans2:=ans2+t*len2[e]; 80 k:=pre[k,1]; 81 end; 82 ans1:=ans1+t; 83 end; 84 85 begin 86 assign(input,'hdoj4322.in'); reset(input); 87 assign(output,'hdoj4322.out'); rewrite(output); 88 readln(cas); 89 for i:=1 to 2000 do 90 if i and 1=1 then fan[i]:=i+1 91 else fan[i]:=i-1; 92 for v:=1 to cas do 93 begin 94 readln(n,m,k); 95 for i:=1 to s do head[i]:=0; 96 tot:=0; s:=0; ans1:=0; ans2:=0; sum:=0; 97 for i:=1 to m do 98 begin 99 read(b[i]); 100 sum:=sum+b[i]; 101 end; 102 for i:=1 to m do 103 for j:=1 to n do read(a[i,j]); 104 source:=n+m+1; src:=n+m+2; s:=n+m+2; 105 for i:=1 to n do add(source,i,1,0); 106 for i:=1 to m do 107 for j:=1 to n do 108 if a[i,j]=1 then add(j,i+n,1,0); 109 for i:=1 to m do 110 begin 111 add(i+n,src,b[i] div k,k); 112 if b[i] mod k>0 then add(i+n,src,1,b[i] mod k); 113 end; 114 while spfa do mcf; 115 if n-ans1>=sum-ans2 then writeln('Case #',v,': YES') 116 else writeln('Case #',v,': NO'); 117 end; 118 close(input); 119 close(output); 120 end.