POJ2391_Ombrophobic Bovines

时间:2022-07-27 23:12:55

有F个地方,每个地方有一定数量的牛,能够容纳一定数量的牛,某些地方之间有边,表示走两点之间需要消耗的时间。

现在求使得所有的牛都被容纳所需要的最少的时间。

由于时间是一个不确定的因素,我们需要二分。

假设当前二分的时间为t,那么从某一点出发距离不要超过t的点都是可以连边的,于是最后只需要跑最大流验证是否满流即可。

此题给的数据居然爆int,真是深坑啊。

召唤代码君:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define maxn 1122
#define maxm 555555
typedef long long ll;
using namespace std; ll inf=~0U>>;
ll to[maxm],next[maxm],c[maxm],first[maxn],edge;
ll cow[maxn],hold[maxn],d[maxn],tag[maxn],TAG=;
ll Q[maxm],bot,top;
ll dis[maxn][maxn],f[maxn],g[maxn][maxn];
bool can[maxn];
ll n,m,sumcow,ans,s,t; void _init()
{
sumcow=;
for (int i=; i<=n; i++)
for (int j=; j<=n; j++) dis[i][j]=-;
} void spfa(ll x)
{
for (int i=; i<=n; i++) f[i]=inf;
Q[bot=top=]=x,f[x]=;
while (bot<=top)
{
ll cur=Q[bot++];
for (int i=; i<=n; i++)
if (dis[cur][i]!=- && f[cur]+dis[cur][i]<f[i])
{
Q[++top]=i;
f[i]=f[cur]+dis[cur][i];
}
}
for (int i=; i<=n; i++) g[x][i]=f[i];
} void _input()
{
ll U,V,W;
for (int i=; i<=n; i++) scanf("%I64d%I64d",&cow[i],&hold[i]),sumcow+=cow[i];
while (m--)
{
scanf("%I64d%I64d%I64d",&U,&V,&W);
if (dis[U][V]==-) dis[U][V]=dis[V][U]=W;
else if (W<dis[U][V]) dis[U][V]=dis[V][U]=W;
}
for (int i=; i<=n; i++) if (cow[i]>) spfa(i);
} void addedge(ll U,ll V,ll W)
{
edge++;
to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge;
edge++;
to[edge]=U,c[edge]=,next[edge]=first[V],first[V]=edge;
} bool bfs()
{
Q[bot=top=]=t,d[t]=,tag[t]=++TAG;
while (bot<=top)
{
ll cur=Q[bot++];
for (int i=first[cur]; i!=-; i=next[i])
{
if (c[i^]> && tag[to[i]]!=TAG)
{
tag[to[i]]=TAG,Q[++top]=to[i];
d[to[i]]=d[cur]+,can[to[i]]=false;
if (to[i]==s) return true;
}
}
}
return false;
} ll dfs(ll cur,ll num)
{
if (cur==t) return num;
ll tmp=num,k;
for (int i=first[cur]; i!=-; i=next[i])
if (c[i]> && d[to[i]]==d[cur]- && tag[to[i]]==TAG && !can[to[i]])
{
k=dfs(to[i],min(c[i],num));
if (k) num-=k,c[i]-=k,c[i^]+=k;
if (num==) break;
}
if (num) can[cur]=true;
return tmp-num;
} bool check(ll x)
{
s=,t=*n+,edge=-,ans=;
for (int i=s; i<=t; i++) first[i]=-;
for (int i=; i<=n; i++)
{
if (cow[i]>)
{
addedge(s,i,cow[i]);
for (int j=; j<=n; j++)
if (g[i][j]<=x) addedge(i,j+n,cow[i]);
}
addedge(i+n,t,hold[i]);
}
while (bfs()) ans+=dfs(s,inf);
return ans==sumcow;
} int main()
{
inf*=inf;
while (scanf("%I64d%I64d",&n,&m)!=EOF)
{
_init();
_input();
if (!check(inf-))
{
puts("-1");
continue;
}
ll l=,r=inf-,mid;
while (l<r)
{
mid=l/+r/;
if (l&r&) mid++;
if (check(mid)) r=mid;
else l=mid+;
}
printf("%I64d\n",l);
}
return ;
}