poj 2195Going Home

时间:2022-10-27 00:11:15

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的更多相关文章

  1. POJ 2195Going Home&lpar;网络流之最小费用流)

    题目地址:id=2195">POJ2195 本人职业生涯费用流第一发!!快邀请赛了.决定还是多学点东西.起码碰到简单的网络流要A掉.以后最大流费用流最小割就一块刷. 曾经费用流在我心目 ...

  2. POJ 3370&period; Halloween treats 抽屉原理 &sol; 鸽巢原理

    Halloween treats Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 7644   Accepted: 2798 ...

  3. POJ 2356&period; Find a multiple 抽屉原理 &sol; 鸽巢原理

    Find a multiple Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 7192   Accepted: 3138   ...

  4. POJ 2965&period; The Pilots Brothers&&num;39&semi; refrigerator 枚举or爆搜or分治

    The Pilots Brothers' refrigerator Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 22286 ...

  5. POJ 1753&period; Flip Game 枚举or爆搜&plus;位压缩,或者高斯消元法

    Flip Game Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 37427   Accepted: 16288 Descr ...

  6. POJ 3254&period; Corn Fields 状态压缩DP &lpar;入门级&rpar;

    Corn Fields Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 9806   Accepted: 5185 Descr ...

  7. POJ 2739&period; Sum of Consecutive Prime Numbers

    Sum of Consecutive Prime Numbers Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 20050 ...

  8. POJ 2255&period; Tree Recovery

    Tree Recovery Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 11939   Accepted: 7493 De ...

  9. POJ 2752 Seek the Name&comma; Seek the Fame &lbrack;kmp&rsqb;

    Seek the Name, Seek the Fame Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 17898   Ac ...

随机推荐

  1. java Future 接口介绍

    (转自:http://blog.csdn.net/yangyan19870319/article/details/6093481) 在Java中,如果需要设定代码执行的最长时间,即超时,可以用Java ...

  2. Android课程---关于数据存储的学习之总结

  3. JAVA抓取URL

    package com.ais.plugin.analyse.test; import com.ais.plugin.analyse.util.MD5; import java.io.*; impor ...

  4. 使用Vert&period;x构建Web服务器和消息系统

    如果你对Node.js感兴趣,Vert.x可能是你的下一个大事件:一个建立在JVM上一个类似的架构企业制度. 这一部分介绍Vert.x是通过两个动手的例子(基于Vert.x 2.0). 当Node.j ...

  5. Flask开发微电影网站&lpar;五&rpar;

    后台管理页面是系统管理员登录后对网站进行管理的前端页面 后台登录页面,如下图所示 管理员登录后的页面,如下图所示 管理员登录后,在右上角显示的管理员信息,如下图所示 管理员登录后,在页面中间部分的左侧 ...

  6. JVM中对象的回收过程

      当我们的程序开启运行之后就,就会在我们的java堆中不断的产生新的对象,而这是需要占用我们的存储空间的,因为创建一个新的对象需要分配对应的内存空间,显然我的内存空间是固定有限的,所以我们需要对没有 ...

  7. shell 脚本实战笔记&lpar;11&rpar;--Mysql在linux下的安装和简单运维

    前言: linux中安装mysql以及配置的管理, 基础的运维和管理还是需要会一些的. 这边作下笔记, 以求天天向上(^_^). 安装流程:*). 安装mysql-server1). 借助yum检索相 ...

  8. Gitlab 社区版安装部署和维护指南

    因为我的个人网站 restran.net 已经启用,博客园的内容已经不再更新.这篇文章是在 Gitlab 7.4 的环境下配置的,相关内容可能已经过时. 后续做了一次迁移,将 Gitlab 升级到了 ...

  9. Scala快速排序

    Scala 快排 Scala 基本思想:经过一趟排序,把待排对象分成两个独立的部分,一部分的数据大(小)于另一部分,同理,对子对象进行如此处理,以达到所有数据都有序.   package studen ...

  10. mysql中的case when 与if else

    大神说:在sql中,能用if else  就不用case  when 下面来看看,具体为什么,没有搞清楚,如果有大神知道的提供下资料: Mysql的if既可以作为表达式用,也可在存储过程中作为流程控制 ...