越来越感觉网络流+二分还挺常见的啊,而且往往是要求一个最大的量最小的时候用。
题意:有K台机器,C头奶牛,他们之间的距离用一个邻接矩阵表示,每台机器能容纳M头奶牛喝奶。现在给这C头奶牛分配机器,满足两个要求:
1.这C头奶牛可以找到机器(这个条件由M限制)
2.C头奶牛中走的路程最长的奶牛 要让他的路程尽量短。
问这个最长距离的最小值(有点绕。。。)
做法:首先floyd一下,与处理处点对之间的最短路长度。
二分距离,保存原图中<=mid的边,添加超级源汇,s到每头牛建立容量是1的边,每台机器到t建立容量是M的边,跑一遍最大流,如果满流,说明C头牛都可以在mid的限制条件下被分配。取距离最小值即可.
模板就不贴了,构图如下:
int mat[maxn][maxn];
int K,C,M;
int n;//记录牛和机器的总数量
void input()
{
scanf("%d%d%d",&K,&C,&M);
n=K+C;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
{
scanf("%d",&mat[i][j]);
if(mat[i][j]==0&&(i!=j))
mat[i][j]=INF;//表示不连通
}
}
}
void floyd()
{
for(int k=0;k<n;k++){
for(int i=0;i<n;i++){
for(int j=0;j<n;j++)
{
if(mat[i][k]!=INF&&mat[k][j]!=INF)
{
if(mat[i][k]+mat[k][j]<mat[i][j])
mat[i][j]=mat[i][k]+mat[k][j];
}
}
}
}
}
bool check(int mid)
{
int s=n;
int t=n+1;//公有n+2个结点
//
for(int i=0;i<=t;i++)
adj[i]=NULL;
len=0;//重新构图
for(int i=K;i<n;i++)
{
for(int j=0;j<K;j++)
{
if(mat[i][j]<=mid)
{
insert(i,j,1);
}
}
}
for(int i=K;i<n;i++)
insert(s,i,1);
for(int i=0;i<K;i++)
insert(i,t,M);
return sap(t+1,s,t)==C;
}
int main()
{
input();
floyd();
int l=0;
int r=INF;
int ans=-1;
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid))
{
r=mid-1;
ans=mid;
}
else
l=mid+1;
}
printf("%d\n",ans);
return 0;
}
PS:开始没搞清楚题目干嘛给邻接矩阵,那么多输入都是没用的东西。
不过倒是自然地帮你编了号。。。额。。。只要加个s,t,省事了。。。