首页 > 代码库 > BZOJ 1738: [Usaco2005 mar]Ombrophobic Bovines 发抖的牛
BZOJ 1738: [Usaco2005 mar]Ombrophobic Bovines 发抖的牛
Description
约翰的牛们非常害怕淋雨，那会使他们瑟瑟发抖．他们打算安装一个下雨报警器，并且安排了一个撤退计划．他们需要计算最少的让所有牛进入雨棚的时间． 牛们在农场的F(1≤F≤200)个田地上吃草．有P(1≤P≤1500)条双向路连接着这些田地．路很宽，无限量的牛可以通过．田地上有雨棚，雨棚有一定的容量，牛们可以瞬间从这块田地进入这块田地上的雨棚 请计算最少的时间，让每只牛都进入雨棚．
Input
第1行：两个整数F和P;
第2到F+1行：第i+l行有两个整数描述第i个田地，第一个表示田地上的牛数，第二个表示田地上的雨棚容量．两个整数都在0和1000之间．
第F+2到F+P+I行：每行三个整数描述一条路，分别是起点终点，及通过这条路所需的时间（在1和10^9之间）．
Output
一个整数，表示最少的时间．如果无法使牛们全部进入雨棚，输出-1.
题解：
首先floyd处理出点到点之间的最短时间，然后二分一个时间，网络流判断是否全部进入雨棚。
代码：
#include <cstdio>#include <cstring>#include <algorithm>#include<queue>// by zrt// problem:// 无论你在什么时候开始，重要的是开始以后就不要停止。using namespace std ;typedef long long LL ;const double eps(1e-10) ;const int inf(0x3f3f3f3f) ;int f,p;LL INF=0x3f3f3f3f3f3f3f3f;int ni[205],fi[205];LL map[205][205];int S,T;int H[404],X[340000],P[340000],tot;int flow[340000];int d[406];queue<int> q;bool bfs(){ memset(d,0,sizeof d); d[S]=1;q.push(S); while(!q.empty()){ int x=q.front();q.pop(); for(int i=H[x];i;i=X[i]){ if(flow[i]>0&&!d[P[i]]){ d[P[i]]=d[x]+1; q.push(P[i]); } } } return d[T];}int dfs(int x,int a){ int f=a,tmp; if(x==T||a==0) return a; for(int i=H[x];i;i=X[i]){ if(flow[i]>0&&d[P[i]]==d[x]+1){ tmp=dfs(P[i],min(a,flow[i])); a-=tmp; flow[i]-=tmp; flow[i^1]+=tmp; if(!a) break; } } if(f==a) d[x]=-1;// printf("%d\n",f-a); return f-a;}int Dinic(){ int f=0; while(bfs()) f+=dfs(S,inf); return f;}inline void add(int x,int y,int z){ P[++tot]=y;X[tot]=H[x];H[x]=tot;flow[tot]=z;}int sum=0;bool judge(LL lim){ tot=1;memset(H,0,sizeof H); for(int i=1;i<=f;i++){ add(S,i<<1,ni[i]); add(i<<1,S,0); add(i<<1,i<<1|1,inf); add(i<<1|1,i<<1,0); add(i<<1|1,T,fi[i]); add(T,i<<1|1,0); } for(int i=1;i<=f;i++){ for(int j=1;j<=f;j++){ if(i!=j) { if(map[i][j]<=lim){ add(i<<1,j<<1|1,inf); add(j<<1|1,i<<1,0); } } } } if(Dinic()==sum) return true; else return false;}int main(){ #ifdef LOCAL freopen("in.txt","r",stdin) ; freopen("out.txt","w",stdout) ; #endif scanf("%d%d",&f,&p); S=0,T=1; for(int i=1;i<=f;i++) scanf("%d%d",&ni[i],&fi[i]),sum+=ni[i]; memset(map,0x3f,sizeof map); for(int i=0,x,y,z;i<p;i++){ scanf("%d%d%d",&x,&y,&z); map[x][y]=map[y][x]=min(map[x][y],(LL)z); // map[x][y]=z; } for(int k=1;k<=f;k++){ for(int i=1;i<=f;i++){ if(i==k) continue; for(int j=1;j<=f;j++){ if(i==j||k==j) continue; map[i][j]=min(map[i][j],map[i][k]+map[k][j]); } } } if(!judge(INF-1)) { puts("-1"); return 0; } LL l=-1,r=INF-1,m; while(r-l>1){ m=(l+r)/2; if(judge(m)){ r=m; }else l=m; } printf("%lld\n",r); return 0 ;}
BZOJ 1738: [Usaco2005 mar]Ombrophobic Bovines 发抖的牛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。