【最大流】bzoj1711: [Usaco2007 Open]Dining吃饭
2024-09-06 01:22:00
正在网络流入门(原来这种题用网络流做)
Description
农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食. 每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料. 农夫JOHN做了F (1 <= F <= 100) 种食品并准备了D (1 <= D <= 100) 种饮料. 他的N ( 1 <= N <= 100)头牛都以决定了是否愿意吃某种食物和喝某种饮料. 农夫JOHN想给每一头牛一种食品和一种饮料,使得尽可能多的牛得到喜欢的食物和饮料. 每一件食物和饮料只能由一头牛来用. 例如如果食物2被一头牛吃掉了,没有别的牛能吃食物2.
Input
* 第一行: 三个数: N, F, 和 D
* 第2..N+1行: 每一行由两个数开始F_i 和D_i, 分别是第i 头牛可以吃的食品数和可以喝的饮料数.下F_i个整数是第i头牛可以吃的食品号,再下面的D_i个整数是第i头牛可以喝的饮料号码.
Output
* 第一行: 一个整数,最多可以喂饱的牛数.
题目分析
首先将源点连向所有食物;所有饮料连向汇点。接下来是中间奶牛的部分,容易发现如果简单地食物-奶牛-饮料一连,将会导致一头奶牛可能吃了很多饮料食物。这里有一种巧妙的处理方法:将一头奶牛拆成两个点,中间连一条容量为1的边,意味着一头牛只能占有一个食物/饮料。
话说这题在bzoj为什么会莫名其妙TLE啊……
#include<bits/stdc++.h>
const int maxn = ;
const int maxm = ;
const int INF = 2e9; struct Edge
{
int u,v,f,c;
Edge(int a=, int b=, int c=, int d=):u(a),v(b),f(c),c(d) {}
}edges[maxm];
int n,f,d,S,T,lv[maxn];
int edgeTot,head[maxn],nxt[maxm]; int read()
{
char ch = getchar();
int num = , fl = ;
for (; !isdigit(ch); ch = getchar())
if (ch=='-') fl = -;
for (; isdigit(ch); ch = getchar())
num = (num<<)+(num<<)+ch-;
return num*fl;
}
void addedge(int u, int v, int c)
{
edges[edgeTot] = Edge(u, v, , c), nxt[edgeTot] = head[u], head[u] = edgeTot++;
edges[edgeTot] = Edge(v, u, , ), nxt[edgeTot] = head[v], head[v] = edgeTot++;
}
bool buildLevel()
{
memset(lv, , sizeof lv);
std::queue<int> q;
q.push(S), lv[S] = ;
for (int tmp; q.size(); )
{
tmp = q.front(), q.pop();
for (int i=head[tmp]; i!=-; i=nxt[i])
{
int v = edges[i].v;
if (!lv[v]&&edges[i].f < edges[i].c){
lv[v] = lv[tmp]+, q.push(v);
if (v==T) return true;
}
}
}
return false;
}
int fndPath(int x, int lim)
{
if (x==T) return lim;
for (int i=head[x]; i!=-; i=nxt[i])
{
int v = edges[i].v, val;
if (lv[x]+==lv[v]&&edges[i].f < edges[i].c){
if ((val = fndPath(v, std::min(lim, edges[i].c-edges[i].f)))){
edges[i].f += val, edges[i^].f -= val;
return val;
}else lv[v] = -;
}
}
return ;
}
int dinic()
{
int ret = , val;
while (buildLevel())
while ((val = fndPath(S, INF))) ret += val;
return ret;
}
int main()
{
memset(head, -, sizeof head);
n = read(), f = read(), d = read();
S = , T = n*+f+d+;
for (int i=; i<=n; i++)
{
int k1 = read(), k2 = read();
for (; k1; --k1)
addedge(read(), f+i, );
for (; k2; --k2)
addedge(f+i+n, read()+n*+f, );
addedge(f+i, f+i+n, );
}
for (int i=; i<=f; i++) addedge(S, i, );
for (int i=; i<=d; i++) addedge(f+*n+i, T, );
printf("%d\n",dinic());
return ;
}
END
最新文章
- [Java 基础]方法
- 027医疗项目-模块二:药品目录的导入导出-导入功能的Action的编写
- eclipse luna maven搭建spring mvc
- ASP超级网店V2.5一注入漏洞
- IOS发送Email的两种方法-备
- 每天一个JavaScript实例-推断图片是否载入完毕
- Playground 你不知道的小技巧, CoreData 的使用
- 利用TinyXml进行数据库的热更新
- npoi导入导出
- Android TV开发总结(三)构建一个TV app的焦点控制及遇到的坑
- Angular路由——在路由时候传递数据
- ASP.NET Core 从 gitlab-ci 环境变量读取配置
- docker 私有仓库简易搭建
- SSH出现Connection refused错误
- python接口测试-充值
- 使用Svn的版本号[转载]
- C#通过反射获取对象属性,打印所有字段属性的值
- Git------创建本地库时绿色标志不显示
- 深入理解 js this 绑定机制
- 【ocp-12c】最新Oracle OCP-071考试题库(45题)