就是一个简单题

四个月前a的一道题,今天又看到了,再a一遍吧。

好吧 我想多了 用了bfs求最短路  其实不用的 因为没有障碍物

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define pd(a) printf("%d\n", a);
#define plld(a) printf("%lld\n", a);
#define pc(a) printf("%c\n", a);
#define ps(a) printf("%s\n", a);
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff, LL_INF = 0x7fffffffffffffff;
int n, m, s, t, flow, value;
char str[][];
int head[maxn], d[maxn], cnt, vis[maxn], p[maxn], f[maxn], di[maxn];
int dis[][] = {{, },{, -},{, },{-, }};
vector<int> g;
vector<int> ff; void bfs(int s)
{
mem(di, );
queue<int> Q;
Q.push(s);
di[s] = ;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int i = ; i < ; i++)
{
int v = u + dis[i][] * m + dis[i][];
if(u % m == && i == || (u - ) % m == && i == ) continue;
if(v < || v > n * m || di[v]) continue;
di[v] = di[u] + ;
Q.push(v);
}
}
} struct node
{
int u, v, c, w, next;
}Node[maxn]; void add_(int u, int v, int w, int c)
{
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].w = w;
Node[cnt].c = c;
Node[cnt].next = head[u];
head[u] = cnt++;
} void add(int u, int v, int w, int c)
{
add_(u, v, w, c);
add_(v, u, -w, );
} int spfa()
{
for(int i = ; i < maxn; i++) d[i] = INF;
queue<int> Q;
mem(vis, );
mem(p, -);
Q.push(s);
vis[s] = ;
d[s] = ;
p[s] = ; f[s] = INF;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
vis[u] = ;
// cout << u << endl;
for(int i = head[u]; i != -; i = Node[i].next)
{
node e = Node[i];
//cout << e.v << endl;
if(d[e.v] > d[u] + e.w && e.c > )
{
d[e.v] = d[u] + e.w;
p[e.v] = i;
f[e.v] = min(f[u], e.c);
if(!vis[e.v])
{
vis[e.v] = ;
Q.push(e.v);
// cout << 11111 << endl;
}
}
}
}
if(p[t] == -) return ;
flow += f[t]; value += f[t] * d[t];
for(int i = t; i != s; i = Node[p[i]].u)
{
Node[p[i]].c -= f[t];
Node[p[i] ^ ].c += f[t];
}
return ;
} void max_flow()
{
flow = value = ;
while(spfa());
printf("%d\n", value);
} int main()
{
while(cin >> n >> m && n + m)
{
s = , t = n * m + ;
mem(head, -);
cnt = ;
g.clear(); ff.clear();
for(int i = ; i <= n; i++)
{
scanf("%s", str[i] + );
for(int j = ; j <= m; j++)
{
if(str[i][j] == 'm')
g.push_back((i - ) * m + j), add(s, (i - ) * m + j, , );
else if(str[i][j] == 'H')
ff.push_back((i - ) * m + j), add((i - ) * m + j, t, , );
}
}
for(int i = ; i < g.size(); i++)
{
bfs(g[i]);
for(int j = ; j < ff.size(); j++)
{
add(g[i], ff[j], di[ff[j]] - , );
// cout << g[i] << " " << ff[j] << " " << di[ff[j]] - 1 << endl;
}
}
max_flow(); } return ;
}

最新文章

  1. IIS下配置PHP
  2. phalcon: 当删除循环删除一组数据,需要判断影响的行affectedRows
  3. [HIMCM暑期班]第1课:概述
  4. CentOS 配置防火墙操作实例(启、停、开、闭端口)
  5. 删除oracle表报ORA-24005错误
  6. C# 毕业证书打印《二》
  7. 在C#中子线程如何操作主线程中窗体上控件
  8. hbase meta表修复
  9. 禁用 Browser Link,在浏览器调试的时候回出现大量的get,post数据。
  10. Guess
  11. C#位移运算符
  12. LeetCode_Combinations
  13. DBV-00111: OCI failure (3722) (ORA-01002: fetch out of sequence解决
  14. 【C++模版之旅】项目中一次活用C++模板(traits)的经历
  15. C#中int32 的有效值范围
  16. HDU - 3567 IDA* + 曼哈顿距离 + 康托 [kuangbin带你飞]专题二
  17. [UE4]Spline Mesh Actor
  18. Ubuntu 18.04 Numix主题安装设置
  19. poj 1256 按一定顺序输出全排列(next_permutation)
  20. &lt;spark&gt; hadoop/spark 集群搭建

热门文章

  1. C#.NET 大型通用信息化系统集成快速开发平台 4.0 版本 - 客户常用问题回答
  2. Django的model form组件
  3. 我的微信小程序第三篇(app.json)
  4. Python_练习题_49
  5. codeforces#766 D. Mahmoud and a Dictionary (并查集)
  6. Thrift序列化与反序列化
  7. Vue向后端请求课程展示
  8. ocrosoft 程序设计提高期末复习问题M 递归求猴子吃桃
  9. html js 表单提交前检测数据
  10. asp.net Json序列化