网络流问题最关键的是建图，图建立好了之后，就可以用EK或者DINIC算法来解决问题了。
例题：
POJ 3281 Dining
Description
有N头牛，F种食物，D种饮料，第i头牛...
网络流问题最关键的是建图，图建立好了之后，就可以用EK或者DINIC算法来解决问题了。
例题：
POJ 3281 Dining
Description
有N头牛，F种食物，D种饮料，第i头牛喜欢Fi种食物，Di种饮料,已知一头牛最多能吃一种食物和一种饮料，每种饮料或食物最多能被一头牛吃，求以上条件下，最多能有多少头牛能吃到他所喜爱的食物和饮料
Input
第一行为三个整数N,F,D分别表示牛数，食物数和饮料数，之后N行第i行为第i头牛的喜好，每行首先为两个整数f和d表示该头牛喜欢的食物数和饮料数，然后f个数表示其喜欢的食物编号，最后d个数表示其喜欢的饮料编号
Output
输出能够吃到其最喜欢的食物和饮料的牛的数量
Sample Input
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
Sample Output
3
第一遍做的时候图建错了，原因是没有将牛拆成两个节点，导致一头牛可能会出现在多条增广路径上，将牛拆成两个点，并在两点之间连一条容量为一的路径，这样就能保证一头牛只出现在一条增广路径上面了。图如下（图源：https://blog.csdn.net/mengxiang000000/article/details/52086922）：
![\"在这里插入图片描述\"](\"/images/csdn/15456247706154aQ56247780.png\")
版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
