有两个资源供应，而需求只有一个，把需求拆点，限制容量，放中间，其中一个点跟资源1相连，另外一个点与资源2相连，跑最大流。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define INF 1<<30 6 #define maxn 10100 7 #define maxm 1000000 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 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,F,D; 64 while(scanf("%d%d%d",&N,&F,&D) == 3){ 65 S = 0,T = F+D+N+N+1; 66 init(); 67 int tmp; 68 char str[210]; 69 for(int i = 1;i <= F;i++){ 70 scanf("%d",&tmp); 71 add_edge(S,i,tmp); 72 } 73 for(int i = 1;i <= D;i++){ 74 scanf("%d",&tmp); 75 add_edge(F+i,T,tmp); 76 } 77 for(int i = 1;i <= N;i++){ 78 scanf("%s",str); 79 for(int j = 0;j < F;j++){ 80 if(str[j] == 'Y') 81 add_edge(j+1,F+D+i,1); 82 } 83 } 84 for(int i = 1;i <= N;i++){ 85 scanf("%s",str); 86 for(int j = 0;j < D;j++){ 87 if(str[j] == 'Y') 88 add_edge(F+D+N+i,F+j+1,1); 89 } 90 } 91 for(int i = 1;i <= N;i++) 92 add_edge(F+D+i,F+D+N+i,1); 93 int ans = dinic(); 94 printf("%d ",ans); 95 } 96 return 0; 97 }