专栏首页wymPOJ - 2195 Going Home 最小费用最大流

POJ - 2195 Going Home 最小费用最大流

题意:多组输入,n行m列矩阵包含相等个数的 ‘m’ 和 ‘ H ’ 每个men要到达Home,每移动一个格子耗费 1,求最小花费。

题解:很明显每个人都要到达且移动次数最少,即最小花费最大流。

源点->men->Home->汇点建图

#include <iostream>
#include <stdio.h>
#include <queue>
#include <cstring> 
#include <algorithm>
#define il inline
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 1e4;
const int INF = 0x7fffffff;
struct edge {
	int to, capacity, cost, rev;
	edge() {}
	edge(int to, int _capacity, int _cost, int _rev) :to(to), capacity(_capacity), cost(_cost), rev(_rev) {}
};
struct Min_Cost_Max_Flow {
	int V, H[maxn + 5], dis[maxn + 5], PreV[maxn + 5], PreE[maxn + 5];
	vector<edge> G[maxn + 5];
	//调用前初始化
	void Init(int n) {
		V = n;
		for (int i = 0; i <= V; ++i)G[i].clear();
	}
	//加边
	void Add_Edge(int from, int to, int cap, int cost) {
		G[from].push_back(edge(to, cap, cost, G[to].size()));
		G[to].push_back(edge(from, 0, -cost, G[from].size() - 1));
	}
	//flow是自己传进去的变量,就是最后的最大流,返回的是最小费用
	int Min_cost_max_flow(int s, int t, int f, int& flow) {
		int res = 0; fill(H, H + 1 + V, 0);
		while (f) {
			priority_queue <pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
			fill(dis, dis + 1 + V, INF);
			dis[s] = 0; q.push(pair<int, int>(0, s));
			while (!q.empty()) {
				pair<int, int> now = q.top(); q.pop();
				int v = now.second;
				if (dis[v] < now.first)continue;
				for (int i = 0; i < G[v].size(); ++i) {
					edge& e = G[v][i];
					if (e.capacity > 0 && dis[e.to] > dis[v] + e.cost + H[v] - H[e.to]) {
						dis[e.to] = dis[v] + e.cost + H[v] - H[e.to];
						PreV[e.to] = v;
						PreE[e.to] = i;
						q.push(pair<int, int>(dis[e.to], e.to));
					}
				}
			}
			if (dis[t] == INF)break;
			for (int i = 0; i <= V; ++i)H[i] += dis[i];
			int d = f;
			for (int v = t; v != s; v = PreV[v])d = min(d, G[PreV[v]][PreE[v]].capacity);
			f -= d; flow += d; res += d*H[t];
			for (int v = t; v != s; v = PreV[v]) {
				edge& e = G[PreV[v]][PreE[v]];
				e.capacity -= d;
				G[v][e.rev].capacity += d;
			}
		}
		return res;
	}
	int Max_cost_max_flow(int s, int t, int f, int& flow) {
		int res = 0;
		fill(H, H + 1 + V, 0);
		while (f) {
			priority_queue <pair<int, int> > q;
			fill(dis, dis + 1 + V, -INF);
			dis[s] = 0;
			q.push(pair<int, int>(0, s));
			while (!q.empty()) {
				pair<int, int> now = q.top(); q.pop();
				int v = now.second;
				if (dis[v] > now.first)continue;
				for (int i = 0; i < G[v].size(); ++i) {
					edge& e = G[v][i];
					if (e.capacity > 0 && dis[e.to] < dis[v] + e.cost + H[v] - H[e.to]) {
						dis[e.to] = dis[v] + e.cost + H[v] - H[e.to];
						PreV[e.to] = v;
						PreE[e.to] = i;
						q.push(pair<int, int>(dis[e.to], e.to));
					}
				}
			}
			if (dis[t] == -INF)break;
			for (int i = 0; i <= V; ++i)H[i] += dis[i];
			int d = f;
			for (int v = t; v != s; v = PreV[v])d = min(d, G[PreV[v]][PreE[v]].capacity);
			f -= d; flow += d;
			res += d*H[t];
			for (int v = t; v != s; v = PreV[v]) {
				edge& e = G[PreV[v]][PreE[v]];
				e.capacity -= d;
				G[v][e.rev].capacity += d;
			}
		}
		return res;
	}
};
Min_Cost_Max_Flow MCMF;
char str[200][200];
struct Point{
	int x,y;
}men[maxn],hourse[maxn]; 
int cal(int a,int b){
	return abs(men[a].x-hourse[b].x)+abs(men[a].y-hourse[b].y);
}
int main()
{
	int n,m;
	while(scanf("%d %d",&n,&m)&&(n+m)){
		int len1 = 0,len2 =0;
		getchar();
		for(int i=1;i<=n;i++){
			scanf("%s",str[i]+1);
			for(int j=1;j<=m;j++){
				if(str[i][j]=='m')men[++len1].x = i,men[len1].y = j;
				else if(str[i][j]=='H')hourse[++len2].x = i,hourse[len2].y = j;
			}
			getchar();
		}
		
		int s = 0,t = len1+len2+1;
		MCMF.Init(t);
		for(int i=1;i<=len1;i++){
			for(int j=1;j<=len2;j++){
				MCMF.Add_Edge(i,j+len1,1,cal(i,j));
			}
		}
		for(int i=1;i<=len1;i++)MCMF.Add_Edge(s,i,1,0);
		for(int i=1;i<=len2;i++)MCMF.Add_Edge(i+len1,t,1,0);
		int flow = 0;
		printf("%d\n",MCMF.Min_cost_max_flow(s,t,INF,flow));
	//	printf(" %d\n",flow);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDU 6611 K Subsequence (最小费用最大流)

    用户2965768
  • 牛客练习赛19-C-托米航空公司

    链接:https://www.nowcoder.com/acm/contest/111/C 来源:牛客网

    用户2965768
  • CF910A The Way to Home SPFA(队列优化)

    一只青蛙现在在一个数轴上,它现在要从点 111 跳到点 nnn ,它每次可以向右跳不超过 ddd 个单位。比如,它可以从点 xxx 跳到点 x+ax+ax+a ...

    用户2965768
  • HDU 6611 K Subsequence (最小费用最大流)

    用户2965768
  • 【hdu 2544最短路】【Dijkstra算法模板题】

    Dijkstra算法适用于边权为正的情况。它可用于计算正权图上的单源最短路( Single-Source Shortest Paths, SSSP) , 即从单...

    _DIY
  • 挑战程序竞赛系列(66):4.7字符串匹配(1)

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.n...

    用户1147447
  • Kosaraju算法详解

    Kosaraju算法可以求出有向图中的强连通分量个数,并且对分属于不同强连通分量的点进行标记。它的算法描述较为简单: (1) 第一次对图G进行DFS遍历,并在...

    attack
  • 2017.5.13阶段模拟考试

    预计分数:100+50(其实感觉自己写的对)+100 实际分数:100+0+100 P1149 火柴棒等式 题目描述 给你n根火柴棍,你可以拼出多少个形如“A+...

    attack
  • BZOJ2754: [SCOI2012]喵星球上的点名(AC自动机)

    attack
  • hdu1040

    @坤的

扫码关注云+社区

领取腾讯云代金券