网络流 1009(二)
}
}
gap[ dis[u] = mindis+1 ] ++;
u = pre[u];
}
return maxflow;
}
void addEdge(int u,int v,int c )
{
E[NE].c = c;
E[NE].pos = v;
E[NE].next = head[u];
head[u] = NE++;
E[NE].c = 0;
E[NE].pos = u;
E[NE].next = head[v];
head[v] = NE++;
}
int ans;
void floyed()
{
for(int k=1; k<=n; k++)
for(int i=1; i<=n; i++)
{
if(map[i][k]!=INF)
{
for(int j=1; j<=n; j++)
{
if(map[k][j]!=INF&&map[i][j]>map[i][k]+map[k][j])
{
map[i][j]=map[i][k]+map[k][j];
ans=max(map[i][j],ans);
}
}
}
}
}
int main()
{
int k,c,m;
while(cin>>k>>c>>m)
{
ans=-1;
n=k+c;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>
>map[i][j];
//ans=max(ans,map[i][j]);
if(map[i][j]==0)
map[i][j]=INF;
}
floyed();
int low=0,high=ans,mid;
//high的值应该最小为所有点对之间路径中最长的，不是初始时中的最大值，
//由于这个原因wa了几次。……
while(low<=high)
{
NE=0; NV=k+c+2;
memset(head,-1,sizeof(head));
mid=(low+high)/2;
for(int i=1;i<=k;i++)
addEdge(i,k+c+1,m);
for(int i=k+1;i<=k+c;i++)
addEdge(0,i,1);
for(int i=k+1;i<=k+c;i++)//牛与机器建边
for(int j=1;j<=k;j++)
{
if(map[i][j]<=mid)
addEdge(i,j,1);
}
if(sap(0,k+c+1)==c)//mid符合条件，则可以减小。
high=mid-1;
else
low=mid+1;
}
cout<
}
return 0;
}
/*
2 3 2
0 3 2 1 1
3 0 3 2 0
2 3 0 1 0
1 2 1 0 2
1 0 0 2 0
*/