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