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