越來(lái)越感覺(jué)網(wǎng)絡(luò)流+二分還挺常見(jiàn)的啊，而且往往是要求一個(gè)最大的量最小的時(shí)候用。
題意：有K臺(tái)機(jī)器，C頭奶牛，他們之間的距離用一個(gè)鄰接矩陣表示，每臺(tái)機(jī)器能容納M頭奶牛喝奶。現(xiàn)在給這C頭奶牛分配機(jī)器，滿足兩個(gè)要求:
1.這C頭奶牛可以找到機(jī)器（這個(gè)條件由M限制)
2.C頭奶牛中走的路程最長(zhǎng)的奶牛 要讓他的路程盡量短。
問(wèn)這個(gè)最長(zhǎng)距離的最小值（有點(diǎn)繞。。。）
做法：首先f(wàn)loyd一下，與處理處點(diǎn)對(duì)之間的最短路長(zhǎng)度。
二分距離，保存原圖中<=mid的邊，添加超級(jí)源匯，s到每頭牛建立容量是1的邊，每臺(tái)機(jī)器到t建立容量是M的邊，跑一遍最大流，如果滿流，說(shuō)明C頭牛都可以在mid的限制條件下被分配。取距離最小值即可.
模板就不貼了，構(gòu)圖如下：
int mat[maxn][maxn];
int K,C,M;
int n;//記錄牛和機(jī)器的總數(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個(gè)結(jié)點(diǎn)
//
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:開(kāi)始沒(méi)搞清楚題目干嘛給鄰接矩陣，那么多輸入都是沒(méi)用的東西。
不過(guò)倒是自然地幫你編了號(hào)。。。額。。。只要加個(gè)s,t，省事了。。。