题意:

有F种食物和D种饮料,每头牛有各自喜欢的食物和饮料,而且每种食物或者饮料只能给一头牛。

求最多能有多少头牛能同时得到它喜欢的食物或者饮料。

分析:

把每个牛拆点,中间连一条容量为1的边,保证一头牛不会被多个食物或者饮料分配。

然后把饮料和牛连边,食物和另外一边的牛连边,最后增加一个源点和汇点跑最大流。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std; const int maxn = + ;
const int maxnode = + ;
const int INF = 0x3f3f3f3f; int N, F, D; int n, s, t; struct Edge
{
int from, to, cap, flow;
Edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f) {}
}; vector<Edge> edges;
vector<int> G[maxnode]; void init()
{
edges.clear();
for(int i = ; i < n; i++) G[i].clear();
} void AddEdge(int u, int v, int c)
{
edges.push_back(Edge(u, v, c, ));
edges.push_back(Edge(v, u, , ));
int m = edges.size();
G[u].push_back(m - );
G[v].push_back(m - );
} bool vis[maxnode];
int d[maxnode];
int cur[maxnode]; bool BFS()
{
d[s] = ;
queue<int> Q;
Q.push(s);
memset(vis, false, sizeof(vis));
vis[s] = true; while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int i = ; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
int v = e.to;
if(!vis[v] && e.cap > e.flow)
{
vis[v] = true;
d[v] = d[u] + ;
Q.push(v);
}
}
} return vis[t];
} int DFS(int u, int a)
{
if(u == t || a == ) return a;
int flow = , f;
for(int& i = cur[u]; i < G[u].size(); i++)
{
Edge& e = edges[G[u][i]];
int v = e.to;
if(d[v] == d[u] + && (f = DFS(v, min(a, e.cap - e.flow))) > )
{
flow += f;
e.flow += f;
a -= f;
edges[G[u][i]^].flow -= f;
if(a == ) break;
}
}
return flow;
} int Maxflow()
{
int flow = ;
while(BFS())
{
memset(cur, , sizeof(cur));
flow += DFS(s, INF);
}
return flow;
} int main()
{
while(scanf("%d%d%d", &N, &F, &D) == )
{
n = N * + D + F + ;
s = , t = n - ;
init(); //build graph
for(int i = ; i <= F; i++) AddEdge(s, N*+i, );
for(int i = ; i <= D; i++) AddEdge(N*+F+i, t, );
for(int i = ; i <= N; i++) AddEdge(i, i + N, ); for(int i = ; i <= N; i++)
{
int f, d, x; scanf("%d%d", &f, &d);
while(f--)
{
scanf("%d", &x);
AddEdge(N*+x, i, );
}
while(d--)
{
scanf("%d", &x);
AddEdge(N + i, N*+F+x, );
}
} printf("%d\n", Maxflow());
} return ;
}

代码君

最新文章

  1. SQLServer字符操作
  2. ios开发者到真机测试
  3. python 环境问题
  4. 2016031901 - ubuntu15.1安装驱动
  5. IOS 学习笔记 2015-03-24 OC-API-网络访问-案例一
  6. macbookpro2011 光驱坏了如何安装windows7
  7. 《第一行代码》学习笔记11-活动Activity(9)
  8. POJ 3463 最(次)短路条数
  9. C语言ftell()函数
  10. JAVA如何request没有参数的post提交
  11. .net mvc数据库操作添加数据的几中方法
  12. 〖Java〗Eclispe安装和使用viplugin
  13. redis作为mysql的缓存服务器(读写分离)
  14. struts系列:校验(一)XML校验和函数方法校验
  15. (zxing.net)解码
  16. hdu 2030 统计汉字个数
  17. Kubernetes学习之路(九)之kubernetes命令式快速创建应用
  18. [spring] org.objectweb.asm.ClassVisitor.visit(IILjava/lang/String;Ljav 解决
  19. Sql Server 2005如何导入DBF文件?
  20. hdu 1316(大整数)

热门文章

  1. JS类对象实现继续的几种方式
  2. 记录下这周的mysql调优工作
  3. 洛谷P3959 宝藏(模拟退火乱搞)
  4. 关于原生javascript的this,this真是个强大的东东
  5. get_user
  6. 【虚拟机-网络IP】使用 Powershell 设置 VNET 中的静态 IP
  7. 使用ABAP代码提交SAP CRM Survey调查问卷
  8. Verilog设计分频器(面试必看)
  9. momentum公式
  10. java面试基础篇(一)