Going Home HDU - 1533(最大费用最小流)
Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point.
You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.
InputThere are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.
OutputFor each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.
Sample Input
2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0
Sample Output
2
10
28
题意:使得每个m都对应一个H时的最短的路径
题解:找一个源点,连接所有的m,再找一个汇点,使得所有H指向这个汇点。
然后跑一边最大费用最小流就ok了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
const int MAXX=;
const int INF=0x3f3f3f3f; struct node
{
int st;
int to;
int next;
int cap;
int cost;
}edge[MAXX]; char mp[][];
int head[MAXX],tol;
int pre[MAXX],dis[MAXX];
bool vis[MAXX];
int n,m,p; struct node1
{
int x,y;
node1(){}
node1(int a,int b)
{
x=a;
y=b;
}
};
vector<node1> v1,v2; void init()
{
tol=;
memset(head,-,sizeof(head));
v1.clear();
v2.clear();
} void addedge(int u,int v,int cap,int cost)
{
edge[tol].st=u;
edge[tol].to=v;
edge[tol].cap=cap;
edge[tol].cost=cost;
edge[tol].next=head[u];
head[u]=tol++; edge[tol].st=v;
edge[tol].to=u;
edge[tol].cap=;
edge[tol].cost=-cost;
edge[tol].next=head[v];
head[v]=tol++;
} bool SPFA(int s,int t)
{
queue<int> q;
memset(dis,INF,sizeof(dis));
memset(vis,,sizeof(vis));
memset(pre,-,sizeof(pre));
dis[s]=;
vis[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front(); q.pop();
vis[u]=;
for(int i=head[u];i!=-;i=edge[i].next)
{
int to=edge[i].to;
if(edge[i].cap>&&dis[to]>dis[u]+edge[i].cost)
{
dis[to]=dis[u]+edge[i].cost;
pre[to]=i;
if(!vis[to])
{
vis[to]=;
q.push(to);
}
}
}
}
if(pre[t]==-)return ;
return ;
} int minCostMaxFlow(int s,int t)
{
int cost=;
while(SPFA(s,t))
{
int minn=INF;
for(int i=pre[t];i!=-;i=pre[edge[i].st])
minn=min(minn,edge[i].cap); for(int i=pre[t];i!=-;i=pre[edge[i].st])
{
edge[i].cap-=minn;
edge[i^].cap+=minn;
}
cost+=minn*dis[t];
}
return cost;
} int main()
{
while(scanf("%d%d",&n,&m)&&m&&n)
{
getchar();
init();
for(int i=;i<n;i++)
{
scanf("%s",mp[i]);
getchar();
}
for(int i=;i<n;i++)
for(int j=;j<m;j++)
{
if(mp[i][j]=='m')
v1.push_back(node1(i,j));
if(mp[i][j]=='H')
v2.push_back(node1(i,j)); }
int l=v1.size();
int r=v2.size();
for(int i=;i<v1.size();i++)
{ node1 N1=v1[i];
int x=i+;
addedge(,x,,);
for(int j=;j<v2.size();j++)
{
node1 N2=v2[j];
int y=j+l+;
int D=abs(N1.x-N2.x)+abs(N1.y-N2.y);
addedge(x,y,,D);
addedge(y,x,,D);
if(i==l-)
addedge(y,l+r+,,);
}
}
int ans=minCostMaxFlow(,l++r);
printf("%d\n",ans);
}
return ;
}
最新文章
- 【Java并发编程实战】----- AQS(二):获取锁、释放锁
- 2017《时间的朋友》罗振宇跨年演讲ppt
- Devexpress WPF Theme Editor 01
- Code Page 编码
- JNDI解读(转)
- 解决DB2事物日志满、扩充表字段长度和表空间的命令
- SSH hibernate 使用时最好添加访问数据库的编码
- iOS Core Animation学习总结(1)--CALayer常用属性
- JavaScript 的DOM操作
- RobotFramework环境搭建
- SVN打包方法
- php连接mysql数据库(新浪云SAE)
- API创建/更新员工薪水
- GNU中的处理目标文件的若干工具
- JavaScript中如何检测一个变量是一个String类型?
- 磁盘异步I / O在Windows上显示为同步
- SpringBoot读取application.properties文件内容
- Revit API创建详图视图
- PHP性能调优---php-fpm中启用慢日志配置(用于检测执行较慢的PHP脚本)
- 【转载】Delphi下实现鼠标自动点击器