越來越感覺網(wǎng)絡流+二分還挺常見的啊，而且往往是要求一個最大的量最小的時候用。
題意：有K臺機器，C頭奶牛，他們之間的距離用一個鄰接矩陣表示，每臺機器能容納M頭奶牛喝奶?，F(xiàn)在給這C頭奶牛分配機器，滿足兩個要求:
1.這C頭奶牛可以找到機器（這個條件由M限制)
2.C頭奶牛中走的路程最長的奶牛 要讓他的路程盡量短。
問這個最長距離的最小值（有點繞。。。）
做法：首先floyd一下，與處理處點對之間的最短路長度。
二分距離，保存原圖中<=mid的邊，添加超級源匯，s到每頭牛建立容量是1的邊，每臺機器到t建立容量是M的邊，跑一遍最大流，如果滿流，說明C頭牛都可以在mid的限制條件下被分配。取距離最小值即可.
模板就不貼了，構(gòu)圖如下：
int mat[maxn][maxn];
int K,C,M;
int n;//記錄牛和機器的總數(shù)量
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個結(jié)點
//
for(int i=0;i<=t;i++)
adj[i]=NULL;
len=0;//重新構(gòu)圖
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，省事了。。。