hdu4292Food（最大流Dinic算法）

 /*

题意：每一个人都有喜欢的吃的和喝的，每一个人只选择一个数量的吃的和一个数量的喝的，问能满足最多的人数！？

思路：建图很是重要！f-food, p-people, d-drink

建图：  0（源点）--->f--->p---->p'---->d--->t(汇点)

将人拆分很是重要，因为每一个人最多只能有一种选择，也就是p--->p'的最大流量是 1！

如果还是不清楚，看一看下图的例子，将人拆分与不拆分的区别！



*/

1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #include<vector>
  6 #include<queue>
  7 #define N 850
  8 #define M 201000
  9 #define INF 0x3f3f3f3f
 10 using namespace std;
 11 
 12 struct EDGE{
 13     int v, cap, nt;
 14 };
 15 
 16 int first[N];
 17 EDGE g[M];
 18 int cnt;
 19 int n, f, d;
 20 
 21 void addEdge(int u, int v, int cap){
 22     g[cnt].v=v;
 23     g[cnt].cap=cap;
 24     g[cnt].nt=first[u];
 25     first[u]=cnt++;
 26     
 27     g[cnt].v=u;
 28     g[cnt].cap=0;
 29     g[cnt].nt=first[v];
 30     first[v]=cnt++;
 31 }
 32 
 33 int ans, ss;
 34 
 35 queue<int>q;
 36 int dist[N];
 37 
 38 bool bfs(){
 39     memset(dist, 0, sizeof(dist));
 40     dist[0]=1;
 41     q.push(0);
 42     while(!q.empty()){
 43           int u=q.front();
 44         q.pop();
 45         for(int e=first[u]; ~e; e=g[e].nt){
 46                int v=g[e].v;
 47             int cap=g[e].cap;
 48             if(!dist[v] && cap>0){
 49                 dist[v]=dist[u]+1;
 50                 q.push(v);
 51             }
 52         }    
 53     }
 54     if(dist[ss+1]==0) return false;
 55     return true;
 56 }
 57 
 58 int dfs(int u, int flow){
 59     int ff;
 60     if(u==ss+1) return flow;
 61     for(int e=first[u]; ~e; e=g[e].nt){
 62         int v=g[e].v;
 63         int cap=g[e].cap;    
 64         if(dist[v]==dist[u]+1 && cap>0 && (ff=dfs(v, min(cap, flow)))){
 65             g[e].cap-=ff;
 66             g[e^1].cap+=ff;
 67             return ff;
 68         }
 69      }
 70     dist[u]=-1;//表示u节点不能到达汇点！ 
 71     return 0;
 72 }
 73 
 74 void Dinic(){
 75     ans=0;
 76     int d;
 77     while(bfs())
 78          while(d=dfs(0, INF))
 79             ans+=d;
 80 }
 81 
 82 int main(){
 83     while(scanf("%d%d%d", &n, &f, &d)!=EOF){
 84         ss=2*n+f+d;
 85         cnt=0;
 86         memset(first, -1, sizeof(first));
 87         for(int i=1; i<=f; ++i){//源点到吃的建一条有向边，最大流量为吃的的数量 
 88             int x;
 89             scanf("%d", &x);
 90             addEdge(0, i, x);
 91         }
 92 
 93         for(int i=1; i<=d; ++i){//喝的到汇点建一条有向边，最大流量为喝的的数量
 94             int x;
 95             scanf("%d", &x);
 96             addEdge(n*2+f+i, ss+1, x);
 97         }
 98         for(int i=1; i<=n; ++i){//吃的到人建一条有向边，最大流量为1 
 99             getchar();
100             for(int j=1; j<=f; ++j){
101                 char ch;
102                 scanf("%c", &ch);
103                 if(ch=='Y')
104                     addEdge(j, f+i, 1);
105             }
106         }
107 
108         for(int i=1; i<=n; ++i){//人到喝的建一条有向边，最大流量为1 
109             addEdge(f+i, n+f+i, 1);//人属于节点容量，将人进行拆分，因为每一个人只能有一种选择！ 
110             getchar();
111             for(int j=1; j<=d; ++j){
112                 char ch;
113                 scanf("%c", &ch);
114                 if(ch=='Y')
115                     addEdge(n+f+i, f+n*2+j, 1);
116             }
117         }
118 
119         Dinic();
120         printf("%d\n", ans);
121     }
122     return 0;
123 }