poj2054,poj2155
描述
在网格地图上有n个小人和n栋房子。在单位时间内，每个小人都可以水平或垂直地移动一个单位步长到相邻的点。对于每个小人，你需要为他移动的每一步支付一美元的旅行费用，直到他进入一所房子。这项任务很复杂，因为每栋房子只能容纳一个小人。
你的任务是计算把这n个小人送进那n个不同的房子你需要支付的最少的钱。输入是场景的映射，一个"."意味着一个空的空间，一个" H "代表那个点上的房子，一个" m "表示那个点上有一个小人。
你可以把网格地图上的每一个点想象成一个相当大的正方形，那么它可以同时容纳n个小人；此外，如果一个小个子男人踩在一个有房子的格子上，而没有进入那个房子，那也没关系。
投入
输入中有一个或多个测试用例。每种情况都从给出两个整数普通和M的一行开始，其中普通是地图的行数，M是列数。其余的输入将是描述地图的普通行。你可以假设普通和M都在2到100之间，包括2和100。地图上会有相同数量的H和m；最多会有100栋房子。对于普通和m，输入将以0 0终止。
输出
对于每个测试用例，输出一行单整数，这是您需要支付的最小金额，以美元为单位。
样本值输入
2 2
殿下.m
.
.
.
毫米.H
.H.
.H.
.H.
mmmHmmmm
.H.
.H.
.H.
抽样输出
2
来源
太平洋西北2004
考察点：最小费用最大流
#包含标准视频
#包含字符串。h
#包含数学。h
结构编号
int x，y；
}h[200]，m[200]；
int cost[300][300]，cap[300][300]；
int queue[1000000]，status[300]，dis[300]，pre[300]；
int INF=0x7fffffff，sta，end
int main()
int EK()；
int i，j，n，u，s，t，top1，top2，x1，y1，x2，y2；
char c；
while(scanf(%d %d%*c ，n，u)！=EOF)
如果(n==0 u==0)
打破；
top 1=top 2=0；
for(I=1；我我)
for(j=1；j j)
scanf(%c ，
if(c==H )
h[top1].x=I；
h[top1 ].y=j；
}else if(c==m )
m【top 2】x=I；
m【top 2】y=j；
getchar()；
if(top1==0)
printf( 0 \ n )；
继续；
memset(cap，0，sizeof(cap))；
记忆集(成本，0，sizeof(成本));
n=top1
for(I=1；我我)
cap[0][I]=1；
for(I=1；我我)
x1=m[i-1].x；y1=m[i-1].y；
for(j=1；j j)
x2=h[j-1].x；y2=h[j-1]。y；
x2=x2-x1；
如果(x2 0)
x2=-x2；
y2=y2-y1；
如果(y2 0)
y2=-y2；
cap[I][n j]=1；
cost[I][n j]=(x2 y2)；
cost[n j][I]=-(x2 y2)；
for(I=1；我我)
cap[n I][n n 1]=1；
s=0；
sta=0；end=2 * n ^ 1；
s=EK()；
printf(%d\n ，s)；
返回0;
int bfs()
int i，j，base，top，x；
base=top=0；
for(I=0；我=结束；我)
dis[I]=INF；
记忆集(状态，0，sizeof(状态));
queue[top]=0；
状态[0]=1;
dis[0]=0；
而(底部顶部)
x=queue[base]；
状态[x]=0；
for(I=1；我=结束；我)
如果(x！=i cap[x][i])
if(dis[i] (dis[x] cost[x][i]))
dis[I]=dis[x]cost[x][I]；
pre[I]=x；
如果(!状态[我])
状态[I]=1；
queue[top]=I；
if(dis[end]==INF)
返回0;
}否则
返回1;
int EK()
int i，j，s=0，k，min=INF
while(1)
k=bfs()；
如果(k==0)
打破；
for(I=end；我！=0;i=pre[i])
j=pre[I]；
if(min cap[j][i])
min=cap[j][I]；
for(I=end；我！=0;i=pre[i])
j=pre[I]；
s=(cost[j][I]* min)；
cap[j][I]-=min；
cap[I][j]=min；
返回s；
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。