POJ 3281 Dining

题目源：https://vjudge.net/problem/POJ-3281

               http://poj.org/problem?id=3281

模板套用的：https://blog.csdn.net/Adolphrocs/article/details/84368661

题意：农夫约翰为他的N头牛准备了F种食物和D种饮料。每头牛都有各自喜欢的食物和饮料，而每种食物或饮料只能分配给一头牛。最多能有多少头牛同时得到自己喜欢的食物和饮料？

题解：如下建图，做一次最大流

程序：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5010;
const int MAXN_INT = (1 << 29);
const int inf = (1 << 29);
struct Edge{int v, w, nxt;
};
struct node {int in[MAXN],out[MAXN],Flow;
}a[MAXN];bool isFind;
int head[MAXN];
Edge edge[MAXN];
int dis[MAXN], gap[MAXN], ans[MAXN];
int P, n, m, ecnt, aug, maxFlow, k, F, D;void init(){ecnt = maxFlow = 0;memset(gap, 0, sizeof(gap));memset(dis, 0, sizeof(dis));memset(edge, 0, sizeof(edge));memset(head, -1, sizeof(head));gap[0] = n * 2 + F + D + 2;
}void addEdge(int u, int v, int w){edge[ecnt].v = v;edge[ecnt].w = w;edge[ecnt].nxt = head[u];head[u] = ecnt++;
}void Find(int s){int dx, augc, minDis;if(s == n){isFind = true;maxFlow += aug;return;}augc = aug;minDis = n - 1;for(int i = head[s]; i + 1; i = edge[i].nxt){if(edge[i].w > 0){if(dis[s] == dis[edge[i].v] + 1){aug = min(aug, edge[i].w);Find(edge[i].v);if(dis[1] >= n) return;if(isFind){dx = i;break;}aug = augc;}minDis = min(minDis, dis[edge[i].v]);}}if(!isFind){gap[dis[s]]--;if(gap[dis[s]] == 0) dis[1] = n;dis[s] = minDis + 1;gap[dis[s]]++;}else{edge[dx].w -= aug;edge[dx ^ 1].w += aug;}
}int main(){while(scanf("%d%d%d", &n, &F, &D) != EOF){init();int u, v, w, i, j, f, d, x;for (int i = 2; i <= n + 1; i++){addEdge(i, i + n, 1);addEdge(i + n, i, 0);}for (int i = 2 * n + 2; i <= 2 * n + F + 1; i++){addEdge(1, i, 1);addEdge(i, 1, 0);}for (int i = 2 * n + 2 + F; i <= 2 * n + 1 + F + D; i++){addEdge(i, 2 * n + 2 + F + D, 1);addEdge(2 * n + 2 + F + D, i, 0);}for(int i = 2; i <= n + 1; i++){scanf("%d%d",&f, &d);for (int j = 1; j <= f; j++){scanf("%d", &x);addEdge(2 * n + 1 + x, i, 1);addEdge(i ,2 * n + 1 + x, 0);}for (int j = 1; j <= d; j++){scanf("%d", &x);addEdge(i + n, 2 * n + 1 + F + x, 1);addEdge(2 * n + 1 + F + x, i + n, 0);}}n = n * 2 + 2 + F + D;while(dis[1] < n){isFind = 0;aug = MAXN_INT;Find(1);}printf("%d\n", maxFlow);}return 0;
}