http://poj.org/problem?id=2195
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstdlib>
#define maxn 500
using namespace std;
int n,mm;
char g[maxn][maxn];
const int inf=<<; struct node
{
int x,y;
}m[maxn]; struct node1
{
int x,y;
}h[maxn]; int cap[maxn][maxn];
int cost[maxn][maxn];
int flow[maxn][maxn];
int p[maxn];
int s,t;
int main()
{
while(scanf("%d%d",&n,&mm)&&n&&mm)
{
memset(cap,,sizeof(cap));
memset(cost,,sizeof(cost));
int t1=,t2=;
for(int i=; i<n; i++)
{
scanf("%s",g[i]);
for(int j=; j<mm; j++)
{
if(g[i][j]=='m')
{
m[++t1].x=i;
m[t1].y=j;
}
else if(g[i][j]=='H')
{
h[++t2].x=i;
h[t2].y=j;
}
}
}
for(int i=; i<=t1; i++)
{
cap[][i]=;
cost[][i]=;
}
for(int i=; i<=t1; i++)
{
for(int j=; j<=t2; j++)
{
cap[i][t1+j]=;
cost[i][t1+j]=abs(m[i].x-h[j].x)+abs(m[i].y-h[j].y);
cost[t1+j][i]=-cost[i][t1+j];
}
}
for(int j=; j<=t2; j++)
{
cap[t1+j][t1+t2+]=;
cost[t1+j][t1+t2+]=;
}
s=,t=t1+t2+;
queue<int>q;
int d[maxn];
memset(flow,,sizeof(flow));
int c=,f=;
for(;;)
{
bool inq[maxn];
for(int i=; i<=t1+t2+; i++) d[i]=(i==?:inf);
memset(inq,,sizeof(inq));
q.push(s);
while(!q.empty())
{
int u=q.front();q.pop();
inq[u]=false;
for(int v=; v<=t1+t2+; v++) if(cap[u][v]>flow[u][v] && d[v]>d[u]+cost[u][v])
{
d[v]=d[u]+cost[u][v];
p[v]=u;
if(!inq[v])
{
inq[v]=true;
q.push(v);
}
}
}
if(d[t]==inf) break;
int a=inf;
for(int u=t; u!=s; u=p[u])
{
if(cap[p[u]][u]-flow[p[u]][u]<a)
{
a=cap[p[u]][u]-flow[p[u]][u];
}
}
for(int u=t; u!=s; u=p[u])
{
flow[p[u]][u]+=a;
flow[u][p[u]]-=a;
}
c+=d[t]*a;
f+=a;
}
printf("%d\n",c);
}
return ;
}
poj 2195Going Home的更多相关文章
-
POJ 2195Going Home(网络流之最小费用流)
题目地址:id=2195">POJ2195 本人职业生涯费用流第一发!!快邀请赛了.决定还是多学点东西.起码碰到简单的网络流要A掉.以后最大流费用流最小割就一块刷. 曾经费用流在我心目 ...
-
POJ 3370. Halloween treats 抽屉原理 / 鸽巢原理
Halloween treats Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 7644 Accepted: 2798 ...
-
POJ 2356. Find a multiple 抽屉原理 / 鸽巢原理
Find a multiple Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 7192 Accepted: 3138 ...
-
POJ 2965. The Pilots Brothers&#39; refrigerator 枚举or爆搜or分治
The Pilots Brothers' refrigerator Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 22286 ...
-
POJ 1753. Flip Game 枚举or爆搜+位压缩,或者高斯消元法
Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 37427 Accepted: 16288 Descr ...
-
POJ 3254. Corn Fields 状态压缩DP (入门级)
Corn Fields Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 9806 Accepted: 5185 Descr ...
-
POJ 2739. Sum of Consecutive Prime Numbers
Sum of Consecutive Prime Numbers Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 20050 ...
-
POJ 2255. Tree Recovery
Tree Recovery Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11939 Accepted: 7493 De ...
-
POJ 2752 Seek the Name, Seek the Fame [kmp]
Seek the Name, Seek the Fame Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 17898 Ac ...
随机推荐
-
java Future 接口介绍
(转自:http://blog.csdn.net/yangyan19870319/article/details/6093481) 在Java中,如果需要设定代码执行的最长时间,即超时,可以用Java ...
- Android课程---关于数据存储的学习之总结
-
JAVA抓取URL
package com.ais.plugin.analyse.test; import com.ais.plugin.analyse.util.MD5; import java.io.*; impor ...
-
使用Vert.x构建Web服务器和消息系统
如果你对Node.js感兴趣,Vert.x可能是你的下一个大事件:一个建立在JVM上一个类似的架构企业制度. 这一部分介绍Vert.x是通过两个动手的例子(基于Vert.x 2.0). 当Node.j ...
-
Flask开发微电影网站(五)
后台管理页面是系统管理员登录后对网站进行管理的前端页面 后台登录页面,如下图所示 管理员登录后的页面,如下图所示 管理员登录后,在右上角显示的管理员信息,如下图所示 管理员登录后,在页面中间部分的左侧 ...
-
JVM中对象的回收过程
当我们的程序开启运行之后就,就会在我们的java堆中不断的产生新的对象,而这是需要占用我们的存储空间的,因为创建一个新的对象需要分配对应的内存空间,显然我的内存空间是固定有限的,所以我们需要对没有 ...
-
shell 脚本实战笔记(11)--Mysql在linux下的安装和简单运维
前言: linux中安装mysql以及配置的管理, 基础的运维和管理还是需要会一些的. 这边作下笔记, 以求天天向上(^_^). 安装流程:*). 安装mysql-server1). 借助yum检索相 ...
-
Gitlab 社区版安装部署和维护指南
因为我的个人网站 restran.net 已经启用,博客园的内容已经不再更新.这篇文章是在 Gitlab 7.4 的环境下配置的,相关内容可能已经过时. 后续做了一次迁移,将 Gitlab 升级到了 ...
-
Scala快速排序
Scala 快排 Scala 基本思想:经过一趟排序,把待排对象分成两个独立的部分,一部分的数据大(小)于另一部分,同理,对子对象进行如此处理,以达到所有数据都有序. package studen ...
-
mysql中的case when 与if else
大神说:在sql中,能用if else 就不用case when 下面来看看,具体为什么,没有搞清楚,如果有大神知道的提供下资料: Mysql的if既可以作为表达式用,也可在存储过程中作为流程控制 ...