POJ – 3281 Dining （ISAP EK Dinic）
分类：ACM-图论ACM-图论-网络流
题目大意：有N头牛，F种食物，D种饮料，每种食物和饮料都只有一 现在给出每头牛所喜爱的食物和饮料，问最多有多少头牛能同时得到自己喜欢的食物和饮料
解题思路：将牛拆成两点，权值为1，一条和喜欢的食物相连，权值为1，另一条和喜欢的饮料相连，权值为1 然后将所有食物和超级源点相连，权值为1 将所有的饮料喝超级汇点相连，，权值为1
ISAP
;Edge {int from, to, cap, flow;Edge() {}Edge(int from, int to, int cap, int flow): from(from), to(to), cap(cap), flow(flow) {}};struct ISAP {int p[N], num[N], cur[N], d[N];int t, s, n, m;bool vis[N];vector<int> G[N];vector<Edge> edges;void init(int n) {this->n = n;for (int i = 0; i <= n; i++) {G[i].clear();d[i] = INF;}edges.clear();}void AddEdge(int from, int to, int cap) {edges.push_back(Edge(from, to, cap, 0));edges.push_back(Edge(to, from, 0, 0));int m = edges.size();G[from].push_back(m – 2);G[to].push_back(m – 1);}bool BFS() {memset(vis, 0, sizeof(vis));queue<int> Q;d[t] = 0;vis[t] = 1;Q.push(t);while (!Q.empty()) {int u = Q.front();Q.pop();for (int i = 0; i < G[u].size(); i++) {Edge &e = edges[G[u][i] ^ 1];if (!vis[e.from] && e.cap > e.flow) {vis[e.from] = true;d[e.from] = d[u] + 1;Q.push(e.from);}}}return vis[s];}int Augment() {int u = t, flow = INF;while (u != s) {Edge &e = edges[p[u]];flow = min(flow, e.cap – e.flow);u = edges[p[u]].from;}u = t;while (u != s) {edges[p[u]].flow += flow;edges[p[u] ^ 1].flow -= flow;u = edges[p[u]].from;}return flow;}int Maxflow(int s, int t) {this->s = s; this->t = t;int flow = 0;BFS();if (d[s] > n)return 0;memset(num, 0, sizeof(num));memset(cur, 0, sizeof(cur));for (int i = 0; i < n; i++)if (d[i] < INF)num[d[i]]++;int u = s;while (d[s] <= n) {if (u == t) {flow += Augment();u = s;}bool ok = false;for (int i = cur[u]; i < G[u].size(); i++) {Edge &e = edges[G[u][i]];if (e.cap > e.flow && d[u] == d[e.to] + 1) {ok = true;p[e.to] = G[u][i];cur[u] = i;u = e.to;break;}}if (!ok) {int Min = n;for (int i = 0; i < G[u].size(); i++) {Edge &e = edges[G[u][i]];if (e.cap > e.flow)Min = min(Min, d[e.to]);}if (–num[d[u]] == 0)break;num[d[u] = Min + 1]++;cur[u] = 0;if (u != s)u = edges[p[u]].from;}}return flow;}};ISAP isap;int n, f, d;void init() {int s = 0, t = 2 * n + d + f + 1;isap.init(t);for (int i = 1; i <= f; i++) {isap.AddEdge(0, 2 * n + i, 1);}for (int i = 1; i <= d; i++) {isap.AddEdge(2 * n + f + i, t, 1);}int fi, di, x;for (int i = 1; i <= n; i++) {scanf(“%d%d”, &fi, &di);isap.AddEdge(i, n + i, 1);for (int j = 0; j < fi; j++) {scanf(“%d”, &x);isap.AddEdge(2 * n + x, i, 1);}for (int j = 0; j < di; j++) {scanf(“%d”, &x);isap.AddEdge(n + i, 2 * n + f + x, 1);}}int flow = isap.Maxflow(s, t);printf(“%d\n”, flow);}int main() {while (scanf(“%d%d%d”, &n, &f, &d) != EOF) {init();}return 0;}业精于勤，荒于嬉；行成于思，毁于随。
