【题目来源】https://www.acwing.com/problem/content/2242/【题目描述】奶牛们在吃饭方面十分挑剔。每头奶牛都有自己喜欢的食物和饮料并且不会食用其他不喜欢的食物和饮料。农夫约翰为他的奶牛们做了美味的饭菜但他忘了对照他们的喜好来检查菜单。虽然他可能无法令所有奶牛满意但他想给尽可能多的奶牛提供一顿完整的用餐----既有食物可吃也有饮料可喝。农夫约翰一共烹制了 F 种食物并提供了 D 种饮料。约翰共有 N 头奶牛其中第 i 头奶牛有 Fi 种喜欢的食物以及 Di 种喜欢的饮料。约翰需要给每头奶牛分配一种食物和一种饮料并使得有吃有喝的奶牛数量尽可能大。每种食物或饮料都只有一份所以只能分配给一头奶牛食用。【输入格式】第一行包含三个整数 N,F,D。接下来 N 行其中第 i 行描述第 i 头奶牛的饮食喜好首先包含两个整数 Fi 和 Di表示其喜欢的食物和饮料数量然后包含 Fi 个整数表示其喜欢的食物的种类编号最后包含 Di 个整数表示其喜欢的饮料的种类编号。食物编号从 1 到 F饮料编号从 1 到 D。【输出格式】输出一个整数表示能够有吃有喝的奶牛的最大数量。​​​​​​​【输入样例】4 3 32 2 1 2 3 12 2 2 3 1 22 2 1 3 1 22 1 1 3 3【输出样例】3【样例解释】一种使得三头奶牛满意的可行方法是奶牛 1没饭。奶牛 2食物 2饮料 2。奶牛 3食物 1饮料 1。奶牛 4食物 3饮料 3。【数据范围】1≤N,F,D≤100,1≤Fi≤F,1≤Di≤D【算法分析】拆点等于把 1 个点 拆成 2 个点中间连一条容量受限的边用这条边的容量间接限制原节点的最大流量。拆点是网络流里最常用的建模技巧核心目的是给「单个节点」加上流量限制限制该节点最多被经过 / 使用多少次。本题中一头牛最多只能被选中一次一份食物 一份饮料。如果不拆点流量可以反复经过这头牛对应的节点一头牛会被多次统计答案就错了。【算法代码】#include bits/stdc.h using namespace std; typedef long long LL; const int N4e25,M4e55; const int INF0x3f3f3f3f; int n,m1,m2,S,T; int h[N],e[M],ne[M],f[M],idx; int d[N],cur[N],q[N]; void add(int a,int b,int w) { f[idx]w,e[idx]b,ne[idx]h[a],h[a]idx; f[idx]0,e[idx]a,ne[idx]h[b],h[b]idx; } bool bfs() { memset(d,-1,sizeof d); int hh0,tt0; q[0]S,d[S]0; while(hhtt) { int uq[hh]; for(int ih[u]; ~i; ine[i]) { int ve[i]; if(d[v]-1 f[i]) { d[v]d[u]1; q[tt]v; } } } return d[T]!-1; } int dfs(int u,int lim) { if(uT) return lim; int flow0; for(int icur[u]; ~i flowlim; ine[i]) { cur[u]i; int ve[i]; if(d[v]d[u]1 f[i]) { int tdfs(v,min(f[i],lim-flow)); if(!t) d[v]-1; f[i]-t,f[i^1]t,flowt; } } return flow; } LL dinic() { LL r0,flow0; while(bfs()) { //0~T for(int i0; iT; i) cur[i]h[i]; while(flowdfs(S,INF)) rflow; } return r; } int main() { memset(h,-1,sizeof h); cinnm1m2; S0,Tn*2m1m21; for(int i1; im1; i) add(S,2*ni,1); for(int i1; im2; i) add(2*nm1i,T,1); for(int i1; in; i) { add(i,in,1); int a,b; cinab; while(a--) { int x; cinx; add(n*2x,i,1); } while(b--) { int x; cinx; add(in,n*2m1x,1); } } coutdinic()endl; return 0; } /* in: 4 3 3 2 2 1 2 3 1 2 2 2 3 1 2 2 2 1 3 1 2 2 1 1 3 3 out: 3 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/161317988https://www.acwing.com/solution/content/125942/