nx一个挤奶器，ny奶牛，每个挤奶罐为最m奶牛使用。
现在给nx+ny在矩阵之间的距离。要求使所有奶牛挤奶到挤奶正在旅程，最小的个体奶牛步行距离的最大值。
始感觉这个类似二分图匹配，不同之处在于挤奶器能够连接m个以内的奶牛，用网络流的模型是能够求出满足条件的解的。
问题是怎样满足最大路程的最小值，这一种典型的二分的问法。。
所以我们二分答案，也就是枚举最大路程，直到求得最小值。
每次建边既加入全部最大路程以内的边，加入源点向每一个挤奶器建边。容量为m。其它边都是1，
若返回的最大流是ny则该枚举值能够达到。
这题由于二分上界wa的是由于 有些点之间開始不直接连通，求了floyd之后联通了且边权>200
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define eps 1e-6
#define ll __int64
const int maxn=300;
using namespace std; int n,s,t,level[maxn],c[maxn][maxn];
int m,nx,ny,dis[maxn][maxn]; bool makelevel()
{
memset(level,0,sizeof level);
level[s]=1;
int q[maxn];
int fro=0,iq=0;
q[iq++]=s;
int i,v;
while(fro!=iq)
{
v=q[fro++];
for(i=0;i<=n+1;i++)//注意点的编号
{
if(!level[i]&&c[v][i])
{
level[i]=level[v]+1;
q[iq++]=i;
}
}
}
if(!level[t]) return 0;
return 1;
} int dfs(int now,int maxf)
{
if(now==t) return maxf;
int ret=0;
for(int i=0;maxf&&i<=n+1;i++)//注意点的编号
{
if(c[now][i]&&level[now]+1==level[i])
{
int tmp=dfs(i,min(maxf,c[now][i]));
c[now][i]-=tmp;
c[i][now]+=tmp;
ret+=tmp;
maxf-=tmp;
}
}
return ret;
} int dinic(int d)
{
int i,j;
memset(c,0,sizeof c);
for(i=1;i<=nx;i++)
{
c[s][i]=m;
for(j=nx+1;j<=n;j++)
{
c[j][t]=1;
if(dis[i][j]<=d) c[i][j]=1;
}
}
int ans=0;
while(makelevel()) ans+=dfs(s,inf);
return ans;
} int main()
{
int a,mmax,ri,le,mid,i,j,k;
while(~scanf("%d%d%d",&nx,&ny,&m))
{
mmax=0;
n=nx+ny;
s=0;t=n+1;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
scanf("%d",&a);
if(j>nx&&i<=nx) mmax=max(mmax,a);
dis[i][j]=(a==0?inf:a);
}
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if(i!=j&&dis[i][j]>dis[i][k]+dis[k][j])
dis[i][j]=dis[i][k]+dis[k][j];
}
ri=10000;
le=0;
while(le<ri)
{
mid=(le+ri)/2;
if(dinic(mid)>=ny)
ri=mid;
else le=mid+1;
}
printf("%d\n",ri);
}
return 0;
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。