/*
題意：每一個人都有喜歡的吃的和喝的，每一個人只選擇一個數量的吃的和一個數量的喝的，問能滿足最多的人數！？
思路：建圖很是重要！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 }
?
