首页 > 代码库 > POJ2391_Ombrophobic Bovines

POJ2391_Ombrophobic Bovines

2024-07-12 21:47:49   223人阅读

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

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

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

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

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

 

 

召唤代码君：

 

 

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


联系
我们