题意：老师要把N颗糖分给M个小盆友，M*N的矩阵中的元素(i,j)表示第i个小孩对第j颗糖的喜好，1表示喜欢，0表示不喜欢。如果一个小朋友得到了一颗糖，并且这颗糖是自己喜欢的糖，他会得到K个glad值，否则，只能得到1的glad值。现在告诉你每个小朋友i的glad值要达到B[i]才会开心，问是否存在一种分配方案使得所有的小朋友都能够开心。(1<=N<=13, 1<=M<=13, 2<=K<=10)
记得以前做过一个哈工大OJ上的题，是《网络流建模汇总》上面的例题。也是分糖果的，那个题是说，如果一个孩子被分到了一颗喜欢的糖，glad值+2，如果被分到一颗不喜欢的，glad值+1。那个题采用了这么一种做法：把所有的glad值-1，那么图中的边的容量就只有0和1了，求出最大流maxflow以后，直接判断maxflow+n(糖果数目)>sum(B[i])是不是成立，如果成立就可以给出一个分配方案。maxflow流的意义是所有孩子被分到喜欢的糖的前提下的最大的glad值之和-这些孩子喜欢的糖的数目，那么再加上所有糖的数目n就是能够总体能够达到最大glad值了。
这里，glad值的范围变成了[2,10]，其实做法还是差不多的。
首先建立源点S和汇点T，从S出发向每颗糖i连一条(S,i,K-1)的边。如果第i颗糖可以被小朋友j喜欢,则连一条边(i,j,K-1)。最关键的是从小朋友到汇点T的边应该怎么连。
对于每个小朋友的最小满意度，若B[i]%K>1,连一条(i,T,B[i]%K-1)的边。另外，连一条(i,T,B[i]/K*(K-1) )的边。这样网络中最大流maxflow的意义就是所有孩子被分到喜欢的糖的前提下的最大的glad值之和-这些孩子喜欢的糖的数目了。最后比较maxflow+N和sum(B[i])的大小就可以了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define INF 1<<30 6 #define maxn 30 7 #define maxm 900 8 using namespace std; 9 10 int v[maxm],next[maxm],w[maxm]; 11 int first[maxn],d[maxn],work[maxn],q[maxn]; 12 int e,S,T; 13 int like[14][14]; 14 void init(){ 15 e = 0; 16 memset(first,-1,sizeof(first)); 17 } 18 19 void add_edge(int a,int b,int c){ 20 //printf("add:%d to %d,cap = %d ",a,b,c); 21 v[e] = b;next[e] = first[a];w[e] = c;first[a] = e++; 22 v[e] = a;next[e] = first[b];w[e] = 0;first[b] = e++; 23 } 24 25 int bfs(){ 26 int rear = 0; 27 memset(d,-1,sizeof(d)); 28 d[S] = 0;q[rear++] = S; 29 for(int i = 0;i < rear;i++){ 30 for(int j = first[q[i]];j != -1;j = next[j]) 31 if(w[j] && d[v[j]] == -1){ 32 d[v[j]] = d[q[i]] + 1; 33 q[rear++] = v[j]; 34 if(v[j] == T) return 1; 35 } 36 } 37 return 0; 38 } 39 40 int dfs(int cur,int a){ 41 if(cur == T) return a; 42 for(int &i = work[cur];i != -1;i = next[i]){ 43 if(w[i] && d[v[i]] == d[cur] + 1) 44 if(int t = dfs(v[i],min(a,w[i]))){ 45 w[i] -= t;w[i^1] += t; 46 return t; 47 } 48 } 49 return 0; 50 } 51 52 int dinic(){ 53 int ans = 0; 54 while(bfs()){ 55 memcpy(work,first,sizeof(first)); 56 while(int t = dfs(S,INF)) ans += t; 57 } 58 return ans; 59 } 60 61 int main() 62 { 63 int N,M,K,nkase; 64 scanf("%d",&nkase); 65 for(int kase = 1;kase <= nkase;kase++){ 66 init(); 67 scanf("%d%d%d",&N,&M,&K); 68 S = 0,T = N+M+1; 69 int sum = 0,B; 70 for(int i = 1;i <= N;i++) 71 add_edge(S,i,K-1); 72 for(int i = 1;i <= M;i++){ 73 scanf("%d",&B); 74 sum += B; 75 if(B%K > 1) add_edge(N+i,T,B%K-1); 76 add_edge(N+i,T,B/K*(K-1)); 77 } 78 for(int i = 1;i <= M;i++){//M个小孩 79 for(int j = 1;j <= N;j++){//N颗糖 80 scanf("%d",&like[i][j]); 81 if(like[i][j]) add_edge(j,i+N,K-1); 82 } 83 } 84 int maxflow = dinic(); 85 //printf("maxflow = %d ",maxflow); 86 if(maxflow + N >= sum) printf("Case #%d: YES ",kase); 87 else printf("Case #%d: NO ",kase); 88 } 89 return 0; 90 }