poj 2112 k个挤奶机每天可以给头奶牛让到达大距离小一些代码流.pdfVIP

POJ2112k个挤奶机，每天可以给m头奶牛挤奶，让奶牛到达挤奶机的最大距离最小

思路：先用floyd求解任意两点之间的最短距离，再构建网络，将牛与源点相连容量为1，

将机器与汇点相连容量为m。然后我们二分枚举答案，将牛与机器之间连线小于枚举值得边

加入网络，大于枚举值得边去掉。然后求解最大流

#includeiostream

#includecstdio

#includecstdlib

#includecstring

#includecmath

#includevector

#includequeue

#includeiomanip

#includealgorithm

usingnamespacestd;

typedeflonglongLL;

constintmod=1e9+7;

constdoubleeps=1e-12;

constintinf=1000000;//不要设INT_MAX，floyd的时候会出问题

intc,k,s,t,n,m;

intmap1[300][300];

intflow_map[300][300];

intlevel[300];

voidbuild(intmaxs)

{

memset(flow_map,0,sizeof(flow_map));

for(inti=k+1;i=k+c;i++)flow_map[0][i]=1;//源点到每头牛设一条容量为1

的弧

for(inti=1;i=k;i++)flow_map[i][k+c+1]=m;//机器到汇点设一条容量为m

的弧

for(inti=k+1;i=k+c;i++)

for(intj=1;j=k;j++)

if(map1[i][j]=maxs)flow_map[i][j]=1;//牛与机器之间距离小于maxs的加一条容量为

1的弧

}

voidbfs(intst)

{

memset(level,-1,sizeof(level));

queueintque;

level[st]=0;

que.push(s);

while(!que.empty())

{

intv=que.front();

que.pop();

for(inti=0;in+2;i++)

{

if(flow_map[v][i]0level[i]0)

{

level[i]=level[v]+1;

que.push(i);

}

}

}

}

intdfs(intv,intu,intf)

{

if(vu)returnf;

for(inti=0;in+2;i++)

{

if(flow_map[v][i]0level[v]level[i])

{

intd=dfs(i,u,min(f,flow_map[v][i]));

if(d0)

{

flow_map[v][i]-=d;

flow_map[i][v]+=d;

returnd;

}

}

}

return0;

}

intmax_flow(intst,int