传送门：>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 = 2010; const int MAXM = 100010; const int INF = 1061109567; inline int read(){ int x = 0; int w = 1; register int c = getchar(); while(c ^ '-' && (c < '0' || c > '9')) c = getchar(); if(c == '-') w = -1, c = getchar(); while(c >= '0' && c <= '9') x = (x << 3) +(x << 1) + c - '0', c = getchar(); return x * w; } int N,P,Q,S,T,x; int first[MAXM*2],nxt[MAXM*2],to[MAXM*2],cap[MAXM*2],flow[MAXM*2],num_edge=-1; 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, 0, sizeof(level)); while(!q.empty()) q.pop(); q.push(S); level[S] = 1; int u,v; while(!q.empty()){ u = q.front(); q.pop(); for(int i = first[u]; i != -1; i = nxt[i]){ v = to[i]; if(!level[v] && cap[i]-flow[i] > 0){ level[v] = level[u] + 1; q.push(v); } } } return level[T]!=0; } int DFS(int u, int a){ if(u == T || a == 0) return a; int ans = 0,v,_f; for(int& i = cur[u]; i != -1; i = nxt[i]){ v = to[i]; if(level[u]+1==level[v] && cap[i]-flow[i] > 0){ _f = DFS(v, Min(a, cap[i]-flow[i])); ans += _f, a -= _f; flow[i] += _f, flow[i^1] -= _f; if(a == 0) break; } } return ans; } inline void Dinic(){ int ans = 0; 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=0, T = 2*N+P+Q+2; memset(first, -1, sizeof(first)); for(int i = 1; i <= P; ++i){ add(S, i+2*N, 1, 0); add(i+2*N, S, 0, 0); } for(int i = 1; i <= N; ++i){ for(int j = 1; j <= P; ++j){ x=r; if(x){ add(j+2*N, i, 1, 0); add(i, j+2*N, 0, 0); } } } for(int i = 1; i <= N; ++i){ add(i, i+N, 1, 0); add(i+N, i, 0, 0); } for(int i = 1; i <= N; ++i){ for(int j = 1; j <= Q; ++j){ x=r; if(x){ add(i+N, j+P+2*N, 1, 0); add(j+P+2*N, i+N, 0, 0); } } } for(int i = 1; i <= Q; ++i){ add(P+2*N+i, T, 1, 0); add(T, P+2*N+i, 0, 0); } Dinic(); return 0; }