首页 > 分享 > 洛谷P2402 奶牛隐藏【二分+最大流】

洛谷P2402 奶牛隐藏【二分+最大流】

花匠小妙招
2025-01-06 21:13

题目描述

在一个农场里有n块田地。某天下午，有一群牛在田地里吃草，他们分散在农场的诸多田地上，农场由m条无向的路连接，每条路有不同的长度。

突然，天降大雨，奶牛们非常混乱，想要快点去躲雨。已知每个田地都建立有一个牛棚，但是每个牛棚只能容纳一定数量的牛躲雨，如果超过这个数量，那多出的牛只能去别的田地躲雨。奶牛们每移动1的距离花费1时间，奶牛们想知道它们全部都躲进牛棚，最少需要多少时间。(即最后一头奶牛最少要花多久才能躲进牛棚)。

输入格式：

第一行输入两个整数N,M。N表示田地块数，M表示路径数。

接下来N行，每行两个整数S,P，分别表示该田地现在有几头牛以及该田地的牛棚最多可以容纳多少牛。

接下来M行，每行3个整数A,B,C，表示存在一条路径连接A,B，并且它的长度为C。

输出格式：

一个整数表示所有奶牛全都躲进牛棚所用的最少时间。如果无法使全部奶牛都躲进牛棚，
输出-1。

说明

数据范围 : 对于100%的数据，N<=200 M<=1500

题目分析

一开始还以为是费用流
每次二分最后到达的奶牛所花费的时间建图

Floyd预处理出n个地点两两间最短路
超源向每个田地连边，容量为 s i s_i si
每个牛棚向超汇连边，容量为 p i p_i pi
两两配对每个田地 i i i与牛棚 j j j，若 i i i到 j j j的最短路长度小于等于二分值
从 i i i向 j j j连边，容量为INF

若最大流量等于牛的总数，令R=mid，否则L=mid+1

最后吐槽一下题目数据范围都不给全
为了一个long long和INF调了十几分钟

#include<iostream> #include<cmath> #include<algorithm> #include<queue> #include<cstring> #include<cstdio> using namespace std; typedef long long lt; lt read() { lt f=1,x=0; char ss=getchar(); while(ss<'0'||ss>'9'){if(ss=='-')f=-1;ss=getchar();} while(ss>='0'&&ss<='9'){x=x*10+ss-'0';ss=getchar();} return f*x; } const lt inf=1LL<<50LL; const int maxn=410; int n,m,s,t; struct node{lt v,f,nxt;}E[500010]; int head[maxn],tot; lt lev[maxn],si[maxn],pi[maxn],sum; lt mp[maxn][maxn],maxf,ans=-1; void add(int u,int v,lt f) { E[++tot].nxt=head[u]; E[tot].v=v; E[tot].f=f; head[u]=tot; } void build(lt x) { memset(head,0,sizeof(head)); tot=1; for(int i=1;i<=n;++i) { add(s,i,si[i]); add(i,s,0); add(i+n,t,pi[i]); add(t,i+n,0); for(int j=1;j<=n;++j) { if(mp[i][j]>x) continue; add(i,j+n,inf); add(j+n,i,0); } } } int bfs() { queue<int> q; q.push(s); memset(lev,-1,sizeof(lev)); lev[s]=0; while(!q.empty()) { int u=q.front(); q.pop(); for(lt i=head[u];i;i=E[i].nxt) { int v=E[i].v; if(E[i].f&&lev[v]==-1) { lev[v]=lev[u]+1; if(v==t) return 1; q.push(v); } } } return 0; } lt dfs(lt u,lt cap) { if(u==t) return cap; lt flow=cap; for(lt i=head[u];i;i=E[i].nxt) { lt v=E[i].v; if(E[i].f&&lev[v]==lev[u]+1&&flow) { lt f=dfs(v,min(E[i].f,flow)); flow-=f; E[i].f-=f; E[i^1].f+=f; } } return cap-flow; } int main() { n=read();m=read();t=n*2+1; for(int i=1;i<=n;++i) si[i]=read(),pi[i]=read(),sum+=si[i]; memset(mp,63,sizeof(mp)); for(int i=1;i<=n;++i) mp[i][i]=0; for(int i=1;i<=m;++i) {int u=read(),v=read();lt dis=read();mp[u][v]=mp[v][u]=min(mp[u][v],dis); } for(int k=1;k<=n;++k) for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) mp[i][j]=min(mp[i][j],mp[i][k]+mp[k][j]); lt L=0,R=1LL<<50LL,mid; while(L<R) { mid=L+R>>1; build(mid); maxf=0; while(bfs()) maxf+=dfs(s,inf); if(maxf==sum) ans=mid,R=mid; else L=mid+1; } printf("%lld",ans); return 0; } 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117