/*
做网络流的题建图真的是太重要了!
本题是将人所在的位置和房子所在的位置建立边的联系,其中man到house这一条边的流量为 1, 费用为两者的距离
而方向边的流量为 0, 费用为正向边的相反数(也就是沿着反向边进行增广时,费用要减少,更改先前错误的选择)
最后增加一个源点和一个汇点完毕(源点映射到man, house映射到汇点, 费用为0, 流量为1)
    
*/
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<queue>
#define Max 0x3f3f3f3f
#define N 205
using namespace std; class node
{
public:
int x, y;
}; node xyM[N];
node xyH[N];
int cost[N][N], cap[N][N];
int cntM, cntH;
int pre[N*], dist[N*], vis[N*], n, m; void addE(int i, int j, int ct, int cp)
{
cost[i][j]=ct;
cap[i][j]=cp;
cost[j][i]=-ct;
//cap[j][i]=0;
} int s, t, minCost; void buildMap()
{
int i, j;
memset(cap, , sizeof(cap));
s=; t=cntM+cntH+;
for(i=; i<cntM; ++i)
addE(, i+, , );
for(i=; i<cntH; ++i)
addE(cntM+i+, t, , );
for(i=; i<cntM; ++i)
for(j=; j<cntH; ++j)
addE(i+, cntM+j+, abs(xyM[i].x-xyH[j].x)+abs(xyM[i].y-xyH[j].y), );
} queue<int>q; int spfa()
{
int u, v;
memset(dist, 0x3f, sizeof(dist));
dist[]=;
q.push();
vis[]=;
while(!q.empty())
{
u=q.front();
q.pop();
vis[u]=;
for(v=; v<=t; ++v)
if(cap[u][v]> && dist[v]>dist[u]+cost[u][v])
{
dist[v]=dist[u]+cost[u][v];
pre[v]=u;
if(!vis[v])
{
vis[v]=;
q.push(v);
}
}
}
if(dist[t]==Max)
return ;
return ;
} void updateEdge()
{
int u, minFlow=Max;
for(u=t; u!=s; u=pre[u])//通过最短路径寻找这条路径上的最小流量
if(cap[pre[u]][u]<minFlow)
minFlow=cap[pre[u]][u];
for(u=t; u!=s; u=pre[u])
{
cap[pre[u]][u]-=minFlow;
cap[u][pre[u]]+=minFlow;
minCost+=cost[pre[u]][u];
}
} int main()
{
int i, j;
char c;
while(scanf("%d%d", &n, &m) && (n||m))
{
cntM=cntH=;
minCost=;
for(i=; i<=n; ++i)
{
getchar();
for(j=; j<=m; ++j)
{
scanf("%c", &c);
if(c=='m')
{
xyM[cntM].x=i;
xyM[cntM++].y=j;
}
else if(c=='H')
{
xyH[cntH].x=i;
xyH[cntH++].y=j;
}
}
}
buildMap();
while(spfa())
updateEdge();
printf("%d\n", minCost);
}
return ;
}

//邻接表

 #include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 0x3f3f3f3f
#define N 1000005
using namespace std; int cntH, cntM; struct node{
int x, y;
}; struct EDGE{
int u, v, cap, cost, nt;
};
EDGE edge[N]; queue<int>q;
node man[], house[];
int first[];
int dist[];
int pre[], flow[], vis[];
int cnt, t;
int minCost;
int n, m; void addEdge(int u, int v, int cap, int cost){
edge[cnt].u=u;
edge[cnt].v=v;
edge[cnt].cap=cap;
edge[cnt].nt=first[u];
edge[cnt].cost=cost;
first[u]=cnt++; edge[cnt].u=v;
edge[cnt].v=u;
edge[cnt].cap=;
edge[cnt].nt=first[v];
edge[cnt].cost=-cost;
first[v]=cnt++;
} void buildMap(){
memset(first, -, sizeof(first));
t=cntH+cntM+;
for(int i=; i<=cntM; ++i)
for(int j=; j<=cntH; ++j)
addEdge(i, cntM+j, , abs(man[i].x-house[j].x) + abs(man[i].y-house[j].y));
for(int i=; i<=cntM; ++i)
addEdge(, i, , );
for(int i=; i<=cntH; ++i)
addEdge(cntM+i, t, , );
} bool MCMF(){
memset(dist, 0x3f, sizeof(dist));
memset(vis, , sizeof(vis));
q.push();
flow[]=INF;
dist[]=;
vis[]=;
while(!q.empty()){
int u=q.front(); q.pop();
vis[u]=;
for(int e=first[u]; ~e; e=edge[e].nt){
int v=edge[e].v, cap=edge[e].cap, cost=edge[e].cost;
if(cap> && dist[v]>dist[u]+cost){
dist[v]=dist[u]+cost;
flow[v]=min(flow[u], cap);
pre[v]=e;
if(!vis[v]){
vis[v]=;
q.push(v);
}
}
}
}
if(dist[t]==INF) return false;
minCost+=dist[t];
int x=t;
while(x!=){
edge[pre[x]].cap-=flow[t];
edge[pre[x]^].cap+=flow[t];
x=edge[pre[x]].u;
}
return true;
} int main(){
while(scanf("%d%d", &n, &m) && (n||m)){
cnt=cntH=cntM=;
for(int i=; i<=n; ++i){
getchar();
for(int j=; j<=m; ++j){
char ch;
scanf("%c", &ch);
if(ch=='m'){
man[++cntM].x=i;
man[cntM].y=j;
}
else if(ch=='H'){
house[++cntH].x=i;
house[cntH].y=j;
}
}
}
buildMap();
minCost=;
while(MCMF());
printf("%d\n", minCost);
}
return ;
}

最新文章

  1. Python Locust对指定网站“一键压测”
  2. javascript --- 原型初探七日谈(三)
  3. VS使用Sublime Text 主题
  4. 【bzoj4241】 历史研究
  5. git在公司内部的使用实践(转)
  6. CUDA 程序中的同步
  7. UIView的frame的扩展分类,轻松取出x、y、height、width等值
  8. 【转】 设定linux 系统可用资源
  9. Linux Stu
  10. Hadoop 实现对Value倒序排序
  11. js大小写锁判断
  12. Maven转化为Dynamic Web Module
  13. java中接口实现多态举例
  14. VS2013中调驱动
  15. 摹客iDoc 新功能“柔性工作流”,让设计随需而动
  16. SharePoint 2013 APP 开发示例 (一)List 读写
  17. 10 sed命令的基本用法
  18. spring如何管理mybatis(二) ----- SqlSession的线程安全性
  19. mysql 移除服务,并在cmd下切换目录
  20. Linux下使用logrotate实现日志切换

热门文章

  1. C# IGUID的生成
  2. Usart的单线半双工模式(stm32F10x系列)
  3. Jetty源码分析(一)
  4. Erlang在Windows上开发环境搭建全过程讲解目录
  5. MFC学习随笔(1)
  6. linux配置本地源
  7. 像素&amp;分辨率
  8. 12G服务器在BIOS中收集阵列卡日志(TTY日志)的方法
  9. spi接口的ds1302时钟芯片控制在lcd1602上显示
  10. JFinal 1.5 发布,JAVA极速WEB+ORM框架