http://poj.org/problem?id=3281
#include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #include<map> #include<set> #include<string.h> #include<stdlib.h> #define INF 0x3f3f3f3f #define ll long long using namespace std; int ln = 10, rn = 120, food = 230, drink = 340; int n, m, f, d; int head[1100], level[1100], cnt, s = 0, t = 500; struct edgee{ int to, cap, next; }e[200010]; //cnt从0开始,反向下标为(正向下标^1) void add(int from, int to, int cap){ e[cnt].to = to; e[cnt].cap = cap; e[cnt].next = head[from]; head[from] = cnt++; e[cnt].to = from; e[cnt].cap = 0; e[cnt].next = head[to]; head[to] = cnt++; } //bfs构建层次网络,从s起点,能到达t返回true int bfs(){ memset(level, 0, sizeof level); level[s] = 1; queue<int>que; que.push(s); while (que.size()){ int p = que.front(); que.pop(); for (int i = head[p]; i != -1; i = e[i].next){ if (level[e[i].to] == 0 && e[i].cap > 0){ level[e[i].to] = level[p] + 1; que.push(e[i].to); if (e[i].to == t) return 1; } } } return 0; } //dfs沿着层次网络找增广路 int dfs(int u, int nf){ if (u == t)return nf; for (int i = head[u]; i != -1; i = e[i].next) if (level[e[i].to] == level[u] + 1){ int d = dfs(e[i].to, min(nf, e[i].cap)); if (d){ e[i].cap -= d; e[i ^ 1].cap += d; return d; } } return 0; } //全局定义的s和t的最大流量 int maxflow(){ int ans = 0; while (bfs()) ans += dfs(s, INF); return ans; } int main() { while (~scanf("%d %d %d", &n, &f, &d)){ //初始化 memset(head, -1, sizeof head); cnt = 0; //构图 for (int i = 1; i <= f; i++)//食物与源点 add(s, food + i, 1); for (int i = 1; i <= d; i++)//饮料与汇点 add(drink + i, t, 1); for (int i = 1; i <= n; i++){ add(ln + i, rn + i, 1); //牛左与牛右 scanf("%d %d", &f, &d); while (f--){ //食物与牛左 scanf("%d", &m); add(food + m, ln + i, 1); } while (d--){ //饮料与牛右 scanf("%d", &m); add(rn + i, drink + m, 1); } } printf("%d\n", maxflow()); } }
原文:https://www.cnblogs.com/kang000/p/8778366.html