POJ2195:Going Home——题解
2024-10-21 15:27:55
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 ;
}
最新文章
- BZOJ1492: [NOI2007]货币兑换Cash
- logo新
- 通过分析 JDK 源代码研究 TreeMap 红黑树算法实现
- Mac更换Sublime Text程序图标
- ICE系列之2——ICE的服务与好处
- cname和CDN
- 去除包裹的a标签
- css 权威指南笔记(三)结合css和XHTML
- 减少JAVA GC
- MassMutual Interview Questions
- .net Framework各个版本之间的发展
- Mac下开发ASP.NET Core应用,我用FineUICore!
- 用POLARDB构建客到智能餐饮系统实践
- spring-boot-2.0.3之quartz集成,数据源问题,源码探究
- python之类
- python基础学习23----IO模型(简)
- spring mvc MultipartFile 上传文件 当文件较小时(10k) ,无法上传成功 。
- day5作业购物商城+ATM
- ASP.NET之旅--深入浅出解读IIS架构
- Nhibernate 一对一,一对多,多对多 成功映射
热门文章
- mysql索引 b+树
- Linux命令应用大词典-第10章 Shell相关命令
- Python列表操作大全(非常全)
- TPO-15 C1 The campus newspaper&#39;s reporter position
- Python 作用域和命名空间
- TW实习日记:第22天
- 【转】unity3d 资源文件从MAX或者MAYA中导出的注意事项
- 记一次Log4j2日志无法输出的 心酸史
- C++ ifndef /define/ endif 作用和用法
- hibernate提示Unknown entity: :xxx