POJ 2391--Ombrophobic Bovines(最大流(拆点)+二分+最短路)
Description
The farm has F (1 <= F <= 200) fields on which the cows graze. A set of P (1 <= P <= 1500) paths connects them. The paths are wide, so that any number of cows can traverse a path in either direction.
Some of the farm's fields have rain shelters under which the cows can shield themselves. These shelters are of limited size, so a single shelter might not be able to hold all the cows. Fields are small compared to the paths and require no time for cows to traverse.
Compute the minimum amount of time before rain starts that the siren must be sounded so that every cow can get to some shelter.
Input
* Lines 2..F+1: Two space-separated integers that describe a field. The first integer (range: 0..1000) is the number of cows in that field. The second integer (range: 0..1000) is the number of cows the shelter in that field can hold. Line i+1 describes field i.
* Lines F+2..F+P+1: Three space-separated integers that describe a path. The first and second integers (both range 1..F) tell the fields connected by the path. The third integer (range: 1..1,000,000,000) is how long any cow takes to traverse it.
Output
Sample Input
3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120
Sample Output
110
题意:牛牛一开始分散在各个草场,每个草场存在一个有容纳上限的避难所,草场之间有道路连接(双向),并且路程耗时和道路长度成正比。问当下雨时,所有牛转移至避难所的最短时间。
思路:二分求答案T。先跑一遍floyd求最短路。
构图方面,将每个点拆分成两个点i, i+n,设置源点s和汇点t, 按照 s-->i, i+n-->t,i<-->j 建立网络,容量分别为一开始牛的只数,避难所上限,INF。
对于每一个T,重新构图, 如果对于点i, j, 最短路dis[i][j]<=T,那么i-->j+n 连一条容量为INF的边,表示这两个点的牛能在T时间内转移。
然后求最大流,如果最大流大于等于牛的总只数,那么这个T是满足条件的,继续二分下去。
。。。这道题改了很长时间,最后发现是函数返回long long 和 int 搞乱了。
AC代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
typedef long long LL;
const int MAXN=2e3+;
const int INF=1e9+;
const LL INFLL=1e16+;
struct Edge{
int to;
int c;
int rev;
};
LL dis[MAXN][MAXN];
int sum=,s,t,n,m;
vector<Edge> vec[MAXN];
int in[MAXN],out[MAXN];
int level[MAXN],iter[MAXN];
void floyd(){
for(int k=;k<=n;k++){
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
dis[i][j]=min(dis[i][j], dis[i][k]+dis[k][j]);
}
}
}
return;
}
void add_edge(int a, int b, int cap){
vec[a].push_back((Edge){b, cap, vec[b].size()});
vec[b].push_back((Edge){a, , vec[a].size()-});
return;
} int dfs(int S, int T, int flow){
if(S==T) return flow; for(int &i=iter[S];i<vec[S].size();i++){
Edge &e=vec[S][i];
if(level[S]<level[e.to]&&e.c>){
int d=dfs(e.to, T, min(e.c, flow));
if(d>){
e.c-=d;
vec[e.to][e.rev].c+=d;
return d;
}
}
}
return ;
}
void rebuild(LL T)
{
for(int i=;i<MAXN;i++)
vec[i].clear();
for(int i=;i<=n;i++){
add_edge(s, i, in[i]);
add_edge(i+n, t, out[i]);
add_edge(i, i+n, INF);
}
for(int i=;i<=n;i++){
for(int j=i+;j<=n;j++){
if(dis[i][j]<=T){
add_edge(i, j+n, INF);
add_edge(j, i+n, INF);
}
}
}
}
void bfs(){
memset(level, -, sizeof(level));
queue<int> q;
level[s]=;
q.push(s);
while(!q.empty()){
int v=q.front();q.pop();
for(int i=;i<vec[v].size();i++){
Edge &e=vec[v][i];
if(e.c>&&level[e.to]<){
level[e.to]=level[v]+;
q.push(e.to);
}
}
}
return;
}
int max_flow(LL T){
rebuild(T);
int res=,flow;
while(){
bfs();
if(level[t]<) return res;
memset(iter, , sizeof(iter));
while((flow=dfs(s, t, INF)) > ){
res+=flow;
}
}
//cout<<res<<endl;
return res;
}
LL solve(LL l, LL r){
LL mid,ans=-;
while(l<=r){
mid=(l+r)/;
if(max_flow(mid)>=sum){//dinic算法
ans=mid;
r=mid-;
}
else l=mid+;
//cout<<ans<<endl;
}
return ans;
}
int main()
{
int a,b,w;
scanf("%d %d", &n, &m);
s=,t=*n+;
for(int i=;i<=n;i++){
scanf("%d %d",&in[i], &out[i]);
sum+=in[i];
}
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
dis[i][j]=(i==j)?:INFLL;
for(int i=;i<m;i++){
scanf("%d %d %d", &a, &b, &w);
if(dis[a][b]>w)
dis[a][b]=dis[b][a]=w;
}
floyd();
LL T=solve(, INFLL-);
printf("%lld\n", T);
return ;
}
最新文章
- 剑指Offer-【面试题05:从头到尾打印链表】
- jquery数组(排序)
- 读书笔记——OpenGL超级宝典
- Hibernate 中update hql语句
- ERP系统开发平台 (C#语言,支持多数据库)
- 关于链接target的问题
- R语言画正弦曲线
- 一个Demo就懂的Angular之directive
- 如何利用自己的电脑做服务器发布tomcat的WEB项目供外网访问
- AndroidStudio项目.gitignore文件内容
- (原创)Python 自动化测试框架详解
- documentsUI源码分析
- 深度剖析Redis持久化
- Java多线程——创建线程的两种方式
- php的数组的函数
- 使用sklearn时cannot import name MLPClassifier的解决办法
- Asp.Net Core配置的知识总结
- node.js 使用NAPI写C++插件,(部分转帖)
- eclipse如何使用log4j详解,你get了吗???
- Gson使用技巧
热门文章
- day15生成器send方法,递归,匿名函数,max结合匿名工作原理,常用的内置函数
- Tensorflow实战 手写数字识别(Tensorboard可视化)
- log记录日志使用说明
- Hibernate异常:MappingException
- 在Keras中用Bert进行情感分析
- [Git] 007 三棵树以及向本地仓库加入第一个文件
- <;每日一题>;Day 9:POJ-3281.Dining(拆点 + 多源多汇+ 网络流 )
- 《剑指offer》面试题14 调整数组顺序使奇数位于偶数前面 Java版
- [Codeforces 1191D] Tokitsukaze, CSL and Stone Game(博弈论)
- 如何利用Chrome进行跨域调试