传送门：>Here<
题意：有N个人去酒店，酒店共有P个房间，Q道菜。已知每个人喜欢特定的几个房间和几道菜，一个人是满意的当且仅当住了喜欢的房间，吃了喜欢的菜（一个人只能选一个房间一道菜）。问最多有多少人是满意的
思路分析
利用最大流来解。这题看上去有点像二分图匹配，然而并不是“二分图”。显然只要我们建好图然后跑Dinic即可
如何建图呢？最初的一个想法是容量全部为1，每个人连向源点，再分别连向每道菜，再连向每个房间。然而一看样例跑出来就不对……
首先我们考虑到是人去选择，所以房间和菜肯定都是连人的，因此不能像刚才那样菜去连房间。
考虑把人放在中间，源点先连房间，房间连人，人连菜，菜再连到汇点
貌似没有什么问题？如果一共只有一个人，这个人喜欢三种菜和三种房间，那么按照这种做法答案会跑出来3。震惊，一个人竟然跑出来3！
其实问题就出在对最大流的理解上——最大流仅仅只有对管道容量的约束，并没有对每一个点能容纳多少有约束。在这道题里，一个人最多只能选择一个房间和一道菜，因此有必要把每一个人所能够得到的约束为1。这个其实也很好想，只需要把人拆开，每个人连一条容量为1的边到他的附身，这样即使前面的自己得到了多个匹配，经过后面的这一条管道也就只能流过1了，完美地解决了问题
Code
/*By DennyQi*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define r read()
#define Max(a,b) (((a)>(b)) ? (a) : (b))
#define Min(a,b) (((a)<(b)) ? (a) : (b))
using namespace std;
typedef long long ll;
const int MAXN = ;
const int MAXM = ;
const int INF = ;
inline int read(){
int x = ; int w = ; register int c = getchar();
while(c ^ '-' && (c < '' || c > '')) c = getchar();
if(c == '-') w = -, c = getchar();
while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar(); return x * w;
}
int N,P,Q,S,T,x;
int first[MAXM*],nxt[MAXM*],to[MAXM*],cap[MAXM*],flow[MAXM*],num_edge=-;
int level[MAXN],cur[MAXN];
queue <int> q;
inline void add(int u, int v, int c, int f){
to[++num_edge] = v;
cap[num_edge] = c;
flow[num_edge] = f;
nxt[num_edge] = first[u];
first[u] = num_edge;
}
inline bool BFS(){
memset(level, , sizeof(level));
while(!q.empty()) q.pop();
q.push(S);
level[S] = ;
int u,v;
while(!q.empty()){
u = q.front(); q.pop();
for(int i = first[u]; i != -; i = nxt[i]){
v = to[i];
if(!level[v] && cap[i]-flow[i] > ){
level[v] = level[u] + ;
q.push(v);
}
}
}
return level[T]!=;
}
int DFS(int u, int a){
if(u == T || a == ) return a;
int ans = ,v,_f;
for(int& i = cur[u]; i != -; i = nxt[i]){
v = to[i];
if(level[u]+==level[v] && cap[i]-flow[i] > ){
_f = DFS(v, Min(a, cap[i]-flow[i]));
ans += _f, a -= _f;
flow[i] += _f, flow[i^] -= _f;
if(a == ) break;
}
}
return ans;
}
inline void Dinic(){
int ans = ;
while(BFS()){
for(int i = S; i <= T; ++i) cur[i] = first[i];
ans += DFS(S, INF);
}
printf("%d", ans);
}
int main(){
N=r,P=r,Q=r;
S=, T = *N+P+Q+;
memset(first, -, sizeof(first));
for(int i = ; i <= P; ++i){
add(S, i+*N, , );
add(i+*N, S, , );
}
for(int i = ; i <= N; ++i){
for(int j = ; j <= P; ++j){
x=r;
if(x){
add(j+*N, i, , );
add(i, j+*N, , );
}
}
}
for(int i = ; i <= N; ++i){
add(i, i+N, , );
add(i+N, i, , );
}
for(int i = ; i <= N; ++i){
for(int j = ; j <= Q; ++j){
x=r;
if(x){
add(i+N, j+P+*N, , );
add(j+P+*N, i+N, , );
}
}
}
for(int i = ; i <= Q; ++i){
add(P+*N+i, T, , );
add(T, P+*N+i, , );
}
Dinic();
return ;
}