题目大意是:
K台挤奶机器,C头牛,K不超过30,C不超过200,每台挤奶机器最多可以为M台牛工作,给出这些牛和机器之间,牛和牛之间,机器与机器之间的距离,在保证让最多的牛都有机器挤奶的情况下,给出其中距离最长的一头牛移动距离的最小值。
首先用Floyd求出任意两点之间的最短距离,然后再用二分法限定最多的移动距离d,在求最大流时,搜索增广路的时候同时也判断距离有没有超过d就行了。
#include <cstdio>
#include <cstring>
#include <queue>
#define _clr(x, y) memset(x, y, sizeof(x))
#define Min(x, y) (x < y ? x : y)
#define INF 0x3f3f3f3f
#define N 1005
using namespace std; int flow[N][N], dist[N][N];
int level[N];
int K, C, M, S, T, ln; void Floyd()
{
for(int k=; k<=ln; k++)
for(int i=;i<=ln; i++) if(dist[i][k]<INF)
for(int j=; j<=ln; j++)
if(dist[i][k]+dist[k][j]<dist[i][j])
dist[i][j] = dist[i][k]+dist[k][j];
} bool bfs()
{
_clr(level, -);
level[S] = ;
queue<int> Q;
Q.push(S);
while(!Q.empty())
{
int u = Q.front();
Q.pop();
for(int i=; i<=T; i++)
{
if(flow[u][i] && level[i]<)
{
level[i] = level[u] + ;
Q.push(i);
}
}
}
return level[T]> ? : ;
} int dfs(int x, int f)
{
int a;
if(x==T) return f;
for(int i=; i<=T; i++)
{
if(flow[x][i] && level[i]==level[x]+ && (a=dfs(i,Min(f,flow[x][i]))))
{
flow[x][i] -= a;
flow[i][x] += a;
return a;
}
}
level[x] = -;
return ;
} __int64 Dinic(int len)
{
// 构建残余网络
_clr(flow, );
for(int i=; i<=K; i++)
flow[S][i] = M;
for(int i=K+; i<=ln; i++)
flow[i][T] = ;
for(int i=; i<=K; i++) // 机器
for(int j=K+; j<=ln; j++) // 奶牛
flow[i][j] = (dist[i][j]<=len); // 求解最大流
__int64 ans=, a=;
while(bfs())
while(a=dfs(,INF)) ans += a;
return ans;
} // 二分求解满足条件的最小解
int Slove()
{
int l=, r=;
while(l<=r)
{
int mid = (l+r)>>;
if(Dinic(mid)>=C) r = mid-;
else l = mid+;
}
return l;
}
int main()
{
while(~scanf("%d%d%d", &K, &C, &M))
{
ln = K+C;
T = ln + ;
_clr(dist, );
for(int i=; i<=ln; i++)
for(int j=; j<=ln; j++)
{
scanf("%d", dist[i]+j);
if(dist[i][j]==) dist[i][j]=INF;
}
//// 求出个实体之间的各个最短距离
Floyd(); printf("%d\n", Slove());
}
return ;
}