题目:http://poj.org/problem?id=2195

处理出每个人到每个门的曼哈顿距离,分别建立容量为1费用为曼哈顿距离的边,在源点和每个人人之间建立容量为1费用为0的边,在门和汇点之间建立容量为1费用为0的边,然后跑最小费用流即可。

 #include<cstdio>
#include<cstring>
#include<vector>
#include<queue>
#include<iostream>
#include<stdlib.h>
using namespace std;
typedef pair<int,int> P;
const int maxv = ;
const int inf = 0x3f3f3f3f;
struct edge{
int to,cap,cost,rev;
};
int V;
vector<edge> g[maxv];
int h[maxv];
int dist[maxv];
int prevv[maxv],preve[maxv];
void addedge(int from,int to,int cap,int cost){
edge t;
t.to = to;t.cap = cap;t.cost = cost;t.rev = g[to].size();
g[from].push_back(t);
t.to = from;t.cap = ;t.cost = -cost;t.rev = g[from].size()-;
g[to].push_back(t);
}
int solve(int s,int t,int f){
int res = ;
memset(h,,sizeof(h));
while(f > ){
priority_queue<P,vector<P>,greater<P> > que;
memset(dist,inf,sizeof(dist));
dist[s] = ;
que.push(P(,s));
while(!que.empty()){
P p = que.top();
que.pop();
int v = p.second;
if(dist[v] < p.first)
continue;
for(int i = ;i<g[v].size();i++){
edge &e = g[v][i];
if(e.cap> && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){
dist[e.to] = dist[v]+e.cost+h[v]-h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
que.push(P(dist[e.to],e.to));
}
}
}
if(dist[t] == inf){
return -;
}
for(int i = ;i<=t;i++)
h[i] += dist[i];
int d = f;
for(int i = t;i!=s;i = prevv[i]){
d = min(d,g[prevv[i]][preve[i]].cap);
}
f -= d;
res += d*h[t];
for(int i = t;i!=s;i = prevv[i]){
edge &e = g[prevv[i]][preve[i]];
e.cap -= d;
g[i][e.rev].cap += d;
}
}
return res;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m) && n && m){
vector<P> mm,hh;
char ch;
for(int i = ;i<=n;i++){
for(int j = ;j<=m;j++){
scanf(" %c",&ch);
if(ch == 'm')
mm.push_back(P(i,j));
if(ch == 'H')
hh.push_back(P(i,j));
}
}
for(int i = ;i<=*mm.size()+;i++)
g[i].clear();
for(int i = ;i<mm.size();i++){
for(int j = ;j<hh.size();j++){
addedge(i+,mm.size()+j+,,abs(mm[i].first-hh[j].first)+abs(mm[i].second-hh[j].second));
}
}
int s = ,t = *mm.size()+;
for(int i = ;i<mm.size();i++)
addedge(s,i+,,);
for(int i = ;i<hh.size();i++)
addedge(mm.size()+i+,t,,);
cout << solve(s,t,mm.size()) << endl;
}
}

最新文章

  1. CF719E(线段树+矩阵快速幂)
  2. VBA笔记(四)——立即窗口的使用
  3. windows系统IIS环境下如何部署MVC项目
  4. HANA学习笔记1-搭建HANA学习环境
  5. DDX_Text ()函数 C++
  6. 切换到percona server各种问题
  7. ACM题目————最长回文串
  8. 2天驾驭DIV+CSS (基础篇)(转)
  9. UVA 12647 Balloon
  10. HTTP协议之ETag字段
  11. 【剑指offer】二叉搜索树转双向链表
  12. NodeJS 中npm包管理工具
  13. QT安装后再添加或删除组件
  14. mask rcnn input数据理解
  15. virtualbox中 Ubuntu挂载共享文件夹
  16. hdu5758 思维,树形dp
  17. CentOS 6.5 网络服务器功能的实现②:运用光盘(镜像)制作一个本地yum源
  18. httpclient使用用例
  19. ELK冷热数据分离
  20. (转)mmap和shm共享内存的区别和联系

热门文章

  1. POJ1961[KMP 失配函数]
  2. Redis的安装
  3. 面试题:return和finally执行
  4. Linux用户管理.md
  5. fcntl函数
  6. Java开发环境的搭建以及使用eclipse从头一步步创建java项目
  7. Tech Websites
  8. webapi相关知识
  9. Android开发自学笔记(Android Studio)&mdash;4.界面编程与View组件简单介绍
  10. SpringMVC @RequestBody接收Json对象字符串