题目链接：poj.org/problem?id=3281题目大意：一个农夫有n头牛，f种食物，d种饮料各一份，第i头牛喜欢fi种食物(fi1, fi2…)，di种饮料(di1, di2…)，一头牛只能选择一份搭配（一种食物＋一种饮料）求农夫最多可以同时满足多少头牛的喜好题目分析：第一道拆点建图的题，觉得很有趣，按源点 -> Food -> 牛左 -> 牛右 -> Drink -> 汇点建图，图中牛左 -> 牛右的目的是保证一头牛只选一种食物，方法是给牛左到牛右的边赋值为1，即容量为1，总的定点个数为f + d + 2 * n + 1第一阶段：源点 -> Food => 0 -> (1…f)第二阶段：Food -> 牛左 => (1…f) -> (f + 1, f + n)第三阶段：牛左 -> 牛右 => (f + 1, f + n) -> (f + n + 1, f + 2 * n)第四阶段：牛右 -> Drink => (f + n + 1, f + 2 * n) -> (f + 2 * n + 1, f + 2 * n + d)第五阶段：Drink -> 汇点 => (f + 2 * n + 1, f + 2 * n + d) -> f + 2 * n + d + 1建完图就是裸的最大流，这里用Edmonds-Karp算法求取#include <cstdio>#include <cstring>#include <queue>#include <algorithm>using namespace std;int const INF = INT_MAX;int const MAX = 405;int c[MAX][MAX];int f[MAX][MAX];int a[MAX];int pre[MAX];int n, food, drink;int Edmonds_Karp(int s, int t){int ans = 0;queue <int> q;while(true){memset(a, 0, sizeof(a));a[s] = INF;q.push(s);while(!q.empty()){int u = q.front();q.pop();for(int v = s; v <= t; v++){if(!a[v] && c[u][v] > f[u][v]){a[v] = min(a[u], c[u][v] – f[u][v]);pre[v] = u;q.push(v);}}}if(a[t] == 0)break;for(int u = t; u != s; u = pre[u]){f[pre[u]][u] += a[t];f[u][pre[u]] -= a[t];}ans += a[t];}return ans;}int main(){memset(c, 0, sizeof(c));memset(f, 0, sizeof(f));scanf("%d %d %d", &n, &food, &drink);for(int i = 1; i <= food; i++)c[0][i] = 1;for(int i = 1; i <= n; i++){int nf, nd, getf, getd;scanf("%d %d", &nf, &nd);while(nf –){scanf("%d", &getf);c[getf][food + i] = 1;}c[food + i][food + n + i] = 1;while(nd –){scanf("%d", &getd);c[food + n + i][food + 2 * n + getd] = 1;}}for(int i = 1; i <= drink; i++)c[food + 2 * n + i][food + 2 * n + drink + 1] = 1;printf("%d\n", Edmonds_Karp(0, food + 2 * n + drink + 1));}
，人生难免遇风雨,天空晴朗有阴云,别因雨水湿透衣衫而难过,
