http://acm.hdu.edu.cn/showproblem.php?pid=4292
题意：
给出n个人喜欢的饮料种类以及食物种类，每个人只能取其中一种且数量为1，现在给出有f中食物以及d种饮料，以及他们各自的数量，问如何安、排食物以及饮料，使得最多的人得到一个食物以及一瓶饮料
题解 ：最大流 + 拆点 ；
为了 保证 每一个人只有 一个 食物和 饮料 ，我们 要将 一个人 拆分成 2 个 ，他们之间 连线 流量 为 1 ；
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define INF 0x3fffffff
12 #define F(x) (x)
13 #define N(x) (205+(x))
14 #define CPN(x) (410+(x))
15 #define D(x) (615+(x))
16 #define maxn 250
17 #define CL(a,b) memset(a,b,sizeof(a))
18 #define Pnum 210
19 using namespace std;
20
21 int next[maxn*20],dis[maxn*10];
22 int s,e;
23 int n, fnum ,dnum ,f[maxn],d[maxn],cnt;
24 struct node
25 {
26 int to;
27 int cap ;
28 int next ;
29 }p[200000] ;
30 int que[maxn*maxn] ,idx;
31
32 void add(int x,int y,int cap)
33 {
34 p[cnt].to = y;
35 p[cnt].cap = cap ;
36 p[cnt].next = next[x];
37 next[x] = cnt++ ;
38
39 p[cnt].to = x;
40 p[cnt].cap = 0;
41 p[cnt].next = next[y];
42 next[y] = cnt++ ;
43 }
44 int bfs()// 重新 建 图 （按 层数 建图）
45 {
46
47 memset(dis,0xff,sizeof(dis)) ;
48 dis[s] = 0 ;
49 queue<int>que;
50 que.push(s);
51
52 while(!que.empty())
53 {
54
55 int k = que.front();que.pop() ;
56 for( int i = next[k];i!=-1;i = p[i].next)
57 {
58 int v = p[i].to;
59
60
61 int cap = p[i].cap ;
62
63 if(cap > 0 && dis[v] < 0 )// 如果 可以 可以到达 但 还没有 访问
64 {
65
66 dis[v] = dis[k]+ 1 ;
67 que.push(v) ;
68 }
69 }
70
71 }
72
73
74 if(dis[e] > 0) return 1;
75 else return 0 ;
76
77 }
78
79
80
81 int dfs(int x,int mx)// 查找 路径上的 最小 的 流量
82 {
83
84 int i , a ,tf = 0;
85
86 if(x == e) return mx ;
87
88 for(i = next[x];i!= - 1;i = p[i].next)
89 {
90 int v = p[i].to ;
91 int cap = p[i].cap ;
92 if(cap > 0 && dis[v] == dis[x] + 1 && (a =dfs(v,min(cap,mx))))
93 {
94
95 p[i].cap -= a;
96 p[i^1].cap += a;
97
98 return a;
99
100
101 }
102 }
103 if(!tf) dis[x] = -1;// 没有 找到 最小流量 ，说明 从这个点到不了 终点 ，所以 标记一下
104 return tf ;
105 }
106
107
108
109
110
111 int main()
112 {
113 int i , j ;
114 char c[250] ;
115 //freopen("data.txt","r",stdin) ;
116 while(scanf("%d%d%d",&n,&fnum,&dnum)!=EOF)
117 {
118
119 CL(next,-1) ;
120 cnt = 0;
121 s = 0;
122 e = 2000;
123 for(i = 1 ; i <= fnum;i++)
124 {
125 scanf("%d",&f[i]);
126 }
127 for(i = 1 ; i<= dnum;i++)
128 {
129 scanf("%d",&d[i]) ;
130 }
131 for(i = 1; i <= n;i++)// 人 和 吃的
132 {
133 scanf("%s",c);
134 for(j = 0 ; j< fnum ;j++)
135 {
136 if(c[j] == 'Y')
137 {
138
139 add(j + 1,i + Pnum,1) ;
140 }
141 }
142
143 }
144 for(i = 1; i<= n;i++)// 人 和 喝的
145 {
146 scanf("%s",c);
147 for(j = 0 ; j< dnum ;j++)
148 {
149 if(c[j] == 'Y')
150 {
151
152 add(i + Pnum*2,j + Pnum*3 + 1,1) ;
153 }
154 }
155
156 }
157 for(i = 1; i <= fnum;i++)//增加源点
158 {
159
160 add(0,i,f[i]) ;
161 }
162 for(i = Pnum*3 + 1,j = 1; j <= dnum;i++,j++)//增加 汇点
163 {
164
165 add(i,e,d[j]) ;
166
167 }
168
169 for(i = 1; i <= n;i++)// 将人 拆分
170 {
171
172 add(i + Pnum,i +Pnum*2,1);
173 }
174 int ans = 0;
175 int res;
176
177 while(bfs())
178 {
179
180
181 while(res = dfs(s,INF)) ans+= res ;
182
183 }
184 printf("%d\n",ans);
185 }
186 }
187
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define INF 0x3fffffff
12 #define F(x) (x)
13 #define N(x) (205+(x))
14 #define CPN(x) (410+(x))
15 #define D(x) (615+(x))
16 #define maxn 250
17 #define CL(a,b) memset(a,b,sizeof(a))
18 #define Pnum 210
19 using namespace std;
20
21 int next[maxn*20],dis[maxn*10];
22 int s,e;
23 int n, fnum ,dnum ,f[maxn],d[maxn],cnt;
24 struct node
25 {
26 int to;
27 int cap ;
28 int next ;
29 }p[200000] ;
30 int que[maxn*maxn] ,idx;
31
32 void add(int x,int y,int cap)
33 {
34 p[cnt].to = y;
35 p[cnt].cap = cap ;
36 p[cnt].next = next[x];
37 next[x] = cnt++ ;
38
39 p[cnt].to = x;
40 p[cnt].cap = 0;
41 p[cnt].next = next[y];
42 next[y] = cnt++ ;
43 }
44 int bfs()// 重新 建 图 （按 层数 建图）
45 {
46
47 memset(dis,0xff,sizeof(dis)) ;
48 dis[s] = 0 ;
49 queue<int>que;
50 que.push(s);
51
52 while(!que.empty())
53 {
54
55 int k = que.front();que.pop() ;
56 for( int i = next[k];i!=-1;i = p[i].next)
57 {
58 int v = p[i].to;
59
60
61 int cap = p[i].cap ;
62
63 if(cap > 0 && dis[v] < 0 )// 如果 可以 可以到达 但 还没有 访问
64 {
65
66 dis[v] = dis[k]+ 1 ;
67 que.push(v) ;
68 }
69 }
70
71 }
72
73
74 if(dis[e] > 0) return 1;
75 else return 0 ;
76
77 }
78
79
80
81 int dfs(int x,int mx)// 查找 路径上的 最小 的 流量
82 {
83
84 int i , a ,tf = 0;
85
86 if(x == e) return mx ;
87
88 for(i = next[x];i!= - 1;i = p[i].next)
89 {
90 int v = p[i].to ;
91 int cap = p[i].cap ;
92 if(cap > 0 && dis[v] == dis[x] + 1 && (a =dfs(v,min(cap,mx))))
93 {
94
95 p[i].cap -= a;
96 p[i^1].cap += a;
97
98 return a;
99
100
101 }
102 }
103 if(!tf) dis[x] = -1;// 没有 找到 最小流量 ，说明 从这个点到不了 终点 ，所以 标记一下
104 return tf ;
105 }
106
107
108
109
110
111 int main()
112 {
113 int i , j ;
114 char c[250] ;
115 //freopen("data.txt","r",stdin) ;
116 while(scanf("%d%d%d",&n,&fnum,&dnum)!=EOF)
117 {
118
119 CL(next,-1) ;
120 cnt = 0;
121 s = 0;
122 e = 2000;
123 for(i = 1 ; i <= fnum;i++)
124 {
125 scanf("%d",&f[i]);
126 }
127 for(i = 1 ; i<= dnum;i++)
128 {
129 scanf("%d",&d[i]) ;
130 }
131 for(i = 1; i <= n;i++)// 人 和 吃的
132 {
133 scanf("%s",c);
134 for(j = 0 ; j< fnum ;j++)
135 {
136 if(c[j] == 'Y')
137 {
138
139 add(j + 1,i + Pnum,1) ;
140 }
141 }
142
143 }
144 for(i = 1; i<= n;i++)// 人 和 喝的
145 {
146 scanf("%s",c);
147 for(j = 0 ; j< dnum ;j++)
148 {
149 if(c[j] == 'Y')
150 {
151
152 add(i + Pnum*2,j + Pnum*3 + 1,1) ;
153 }
154 }
155
156 }
157 for(i = 1; i <= fnum;i++)//增加源点
158 {
159
160 add(0,i,f[i]) ;
161 }
162 for(i = Pnum*3 + 1,j = 1; j <= dnum;i++,j++)//增加 汇点
163 {
164
165 add(i,e,d[j]) ;
166
167 }
168
169 for(i = 1; i <= n;i++)// 将人 拆分
170 {
171
172 add(i + Pnum,i +Pnum*2,1);
173 }
174 int ans = 0;
175 int res;
176
177 while(bfs())
178 {
179
180
181 while(res = dfs(s,INF)) ans+= res ;
182
183 }
184 printf("%d\n",ans);
185 }
186 }
187