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

题目大意:

有些人和房子,一个人只能进一个房子,人走到房子的路程即为代价。

求所有人走到房子后的最小代价。

——————————————————

bfs处理每个人到每个房的最短路之后就是裸的费用流了,不解释。

#include<cstdio>
#include<iostream>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cctype>
using namespace std;
typedef long long ll;
const int INF=1e9;
const int N=;
const int M=;
inline int read(){
int X=,w=;char ch=;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();
return w?-X:X;
}
struct node{
int nxt;
int to;
int w;
int b;
}edge[M];
int head[N],cnt=-;
void add(int u,int v,int w,int b){
cnt++;
edge[cnt].to=v;
edge[cnt].w=w;
edge[cnt].b=b;
edge[cnt].nxt=head[u];
head[u]=cnt;
return;
}
int dis[N];
bool vis[N];
inline bool spfa(int s,int t,int n){
deque<int>q;
memset(vis,,sizeof(vis));
for(int i=;i<=n;i++)dis[i]=INF;
dis[t]=;q.push_back(t);vis[t]=;
while(!q.empty()){
int u=q.front();
q.pop_front();vis[u]=;
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
int b=edge[i].b;
if(edge[i^].w&&dis[v]>dis[u]-b){
dis[v]=dis[u]-b;
if(!vis[v]){
vis[v]=;
if(!q.empty()&&dis[v]<dis[q.front()]){
q.push_front(v);
}else{
q.push_back(v);
}
}
}
}
}
return dis[s]<INF;
}
int ans=;
int dfs(int u,int flow,int m){
if(u==m){
vis[m]=;
return flow;
}
int res=,delta;
vis[u]=;
for(int e=head[u];e!=-;e=edge[e].nxt){
int v=edge[e].to;
int b=edge[e].b;
if(!vis[v]&&edge[e].w&&dis[u]-b==dis[v]){
delta=dfs(v,min(edge[e].w,flow-res),m);
if(delta){
edge[e].w-=delta;
edge[e^].w+=delta;
res+=delta;
ans+=delta*b;
if(res==flow)break;
}
}
}
return res;
}
inline int costflow(int S,int T,int n){
while(spfa(S,T,n)){
do{
memset(vis,,sizeof(vis));
dfs(S,INF,T);
}while(vis[T]);
}
return ans;
}
int num1=,num2=;
int mp[][];
int pos[][];
int pdis[][];
bool walk[][];
int dx[]={,-,,};
int dy[]={,,-,};
void bfs(int xx,int yy,int n,int m){
queue<int>q1,q2,q3,q4;
memset(walk,,sizeof(walk));
memset(pdis,,sizeof(pdis));
pdis[xx][yy]=;
q1.push(xx);q2.push(yy);
walk[xx][yy]=;
while(!q1.empty()){
int x=q1.front(),y=q2.front();
q1.pop(),q2.pop();
if(mp[x][y]>){
q3.push(x);q4.push(y);
}
for(int i=;i<;i++){
int nx=x+dx[i],ny=y+dy[i];
if(nx<=||ny<=||nx>n||ny>m||walk[nx][ny])continue;
walk[nx][ny]=;
pdis[nx][ny]=pdis[x][y]+;
q1.push(nx);q2.push(ny);
}
}
while(!q3.empty()){
int nx=q3.front(),ny=q4.front();
q3.pop();q4.pop();
add(pos[xx][yy],mp[nx][ny]+num1,,pdis[nx][ny]);
add(mp[nx][ny]+num1,pos[xx][yy],,-pdis[nx][ny]);
}
return;
}
void restart(){
memset(head,-,sizeof(head));
memset(mp,,sizeof(mp));
memset(pos,,sizeof(pos));
cnt=-;
ans=;
num1=;
num2=;
return;
}
int main(){
int n,m;
while(scanf("%d%d",&n,&m)!=EOF&&n&&m){
restart();
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
char ch;
cin>>ch;
if(ch=='m'){
num1++;
mp[i][j]=-;
pos[i][j]=num1;
}else if(ch=='H'){
num2++;
mp[i][j]=num2;
}
}
}
int S=num1+num2+,T=S+;
for(int i=;i<=num1;i++){
add(S,i,,);
add(i,S,,);
}
for(int i=;i<=num2;i++){
add(i+num1,T,,);
add(T,i+num1,,);
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]==-){
bfs(i,j,n,m);
}
}
}
printf("%d\n",costflow(S,T,T));
}
return ;
}

最新文章

  1. BZOJ1492: [NOI2007]货币兑换Cash
  2. logo新
  3. 通过分析 JDK 源代码研究 TreeMap 红黑树算法实现
  4. Mac更换Sublime Text程序图标
  5. ICE系列之2——ICE的服务与好处
  6. cname和CDN
  7. 去除包裹的a标签
  8. css 权威指南笔记(三)结合css和XHTML
  9. 减少JAVA GC
  10. MassMutual Interview Questions
  11. .net Framework各个版本之间的发展
  12. Mac下开发ASP.NET Core应用,我用FineUICore!
  13. 用POLARDB构建客到智能餐饮系统实践
  14. spring-boot-2.0.3之quartz集成,数据源问题,源码探究
  15. python之类
  16. python基础学习23----IO模型(简)
  17. spring mvc MultipartFile 上传文件 当文件较小时(10k) ,无法上传成功 。
  18. day5作业购物商城+ATM
  19. ASP.NET之旅--深入浅出解读IIS架构
  20. Nhibernate 一对一,一对多,多对多 成功映射

热门文章

  1. mysql索引 b+树
  2. Linux命令应用大词典-第10章 Shell相关命令
  3. Python列表操作大全(非常全)
  4. TPO-15 C1 The campus newspaper&#39;s reporter position
  5. Python 作用域和命名空间
  6. TW实习日记:第22天
  7. 【转】unity3d 资源文件从MAX或者MAYA中导出的注意事项
  8. 记一次Log4j2日志无法输出的 心酸史
  9. C++ ifndef /define/ endif 作用和用法
  10. hibernate提示Unknown entity: :xxx