[文章目录]
Description
约翰的牛们非常害怕淋雨，那会使他们瑟瑟发抖．他们打算安装一个下雨报警器，并且安排了一个撤退计划．他们需要计算最少的让所有牛进入雨棚的时间,牛们在农场的F(1≤F≤200)个田地上吃草．有P(1≤P≤1500)条双向路连接着这些田地．路很宽，无限量的牛可以通过．田地上有雨棚，雨棚有一定的容量，牛们可以瞬间从这块田地进入这块田地上的雨棚 请计算最少的时间，让每只牛都进入雨棚.
floyd+二分+最大流。
求出任意两个点互相到达的最短时间，二分答案，最大流判断是否合法。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int n,m,s,t,lim,sum;
int com[210],out[210];
int head[410],to[101000],nxt[101000],f[101000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
ll mp[210][210];
int dis[410];
queue<int>q;
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
dis[s]=0; q.push(s); int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) return flow;
}
return flow-tmp;
}
bool check(ll x)
{
cnt=1; memset(head,0,sizeof head);
for(int i=1;i<=n;++i) add(s,i,com[i]),add(i+n,t,out[i]),add(i,i+n,inf);
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(i!=j&&mp[i][j]<=x) add(i,j+n,inf);
int flow=0;
while(bfs()) flow+=dinic(s,inf);
return flow==lim;
}
int main()
{
scanf("%d%d",&n,&m); s=n+n+1; t=s+1; int sum=0;
for(int i=1;i<=n;++i)
{
scanf("%d%d",com+i,out+i);
lim+=com[i]; sum+=out[i];
}
if(lim>sum){puts("-1"); return 0;}
memset(mp,0x3f,sizeof mp);
int x,y,z;
while(m--)
{
scanf("%d%d%d",&x,&y,&z);
if(mp[x][y]>z) mp[x][y]=mp[y][x]=z;
}
for(int i=1;i<=n;++i) mp[i][i]=0;
for(int k=1;k<=n;++k)
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(mp[i][k]+mp[k][j]<mp[i][j])
mp[i][j]=mp[i][k]+mp[k][j];
ll l=0,r=0x3f3f3f3fll,mid; r*=n;
while(l<r)
{
mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(check(r)) printf("%lld",r);
//图不连通，无解情况。
//好像二分的时候需要多注意一下无解的情况。。。
else puts("-1");
return 0;
}