# HUNNU11567 Escaping（二分图匹配/最大流）

## Escaping

• Time Limit: 1000ms
• Memory Limit:65536KB
• Total submit users: 18
• Accepted users: 13

### Problem description

One day, Large cruise ”Wu Kong” at sea. The station is represented by a square n*n divided into 1*1 blocks. Unfortunately , ” Wu Kong” hit an iceberg .It will sink after t minutes ,then every people die. However, there will be some life-saving equipment in some rooms(not only one), People from one room to reach another adjacent room (only four) needs one minute .If the people on board to get these life-saving devices so that they will survive, find the greatest number of people can survive.

### Input

The first line contains two integers n and t (2 ≤ n ≤ 10, 1 ≤ t ≤ 10). Each of the next n lines contains n integers(0<=Ai<=9).the people number at this time. Each of the next n more lines contains n integers, Indicates that the room have the number of life-saving equipment(0<=Bi<=9).

### Output

Print a single number — the maximum number of people who will be saved.

### Sample Input

3 3
1 0 0
1 0 0
1 0 0
0 0 0
0 0 0
0 0 3

### Sample Output

2

2014哈尔滨理工大学秋季训练赛

### 链接

http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11567&courseid=144

### 题意

n*n的矩形，表示一些区域有人，一些区域有救生设备，人每次可以向上下左右四个方向移动，移动一次花费1分钟。人现在需要在t分钟内移动至有救生设备的区域（领取一个救生设备）才能逃生，问最多有多少个人可以逃生。

### 代码

• Accepted
• 1532KB
• 15ms
• 3499B
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn = 1100;
const int maxm = 20010;
const int inf = 0x3f3f3f3f;
int a[maxn][maxn], b[maxn][maxn];
int n, t;
int R, S, T;

int dist(int x1, int y1, int x2, int y2)
{
return abs(x1-x2) + abs(y1-y2);
}

struct Edge
{
int u, v, cap;
Edge(){}
Edge(int u, int v, int cap):u(u), v(v),cap(cap){}
}es[maxm];

vector <int> tab[maxn];
int dis[maxn];
int current[maxn];

void addedge(int u, int v, int cap)
{
tab[u].push_back(R);
es[R++] = Edge(u, v, cap);
tab[v].push_back(R);
es[R++] = Edge(v, u, 0);
}

int BFS() // 寻找增广路
{
queue <int> q;
q.push(S);
memset(dis, 0x3f, sizeof(dis));
dis[S] = 0;
while (!q.empty())
{
int h = q.front();
q.pop();
for (int i = 0; i < tab[h].size(); ++i)
{
Edge &e = es[tab[h][i]];
if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)
{
dis[e.v] = dis[h] + 1;
q.push(e.v);
}
}
}
return dis[T] < 0x3f3f3f3f;
}

int dinic(int x, int maxflow)
{
if (x == T)
return maxflow;
for (int i = current[x]; i < tab[x].size(); ++i)
{
current[x] = i; // 当前弧优化
Edge &e = es[tab[x][i]];
if (dis[e.v] == dis[x] + 1 && e.cap > 0)
{
int flow = dinic(e.v, min(maxflow, e.cap));
if (flow)
{
e.cap -= flow;
es[tab[x][i]^1].cap += flow;
return flow;
}
}
}
return 0;
}

int DINIC() // 求解最大流
{
int ans = 0;
while (BFS())
{
int flow;
memset(current, 0, sizeof(current));
while (flow = dinic(S, 0x3f3f3f3f))
ans += flow;
}
return ans;
}

int cnt[maxn][2];

int main()
{
while (scanf("%d%d", &n, &t) != EOF)
{
int tot1 = 0;
S = 0, R = 0; // 源点S，边数R
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
scanf("%d", &a[i][j]);
if (a[i][j] > 0) // 源点与人员连边，权值为每个点的人数
{
addedge(S, ++tot1, a[i][j]);
cnt[tot1][0] = i, cnt[tot1][1] = j;
}
}
}
T = 1010; // 汇点
int tot2 = tot1;
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= n; ++j)
{
scanf("%d", &b[i][j]);
if(b[i][j] > 0) // 汇点与救生设备连边，权值为每个点的救生设备数
{
addedge(++tot2, T, b[i][j]);
cnt[tot2][0] = i, cnt[tot2][1] = j;
}
}
}
for (int i = 1; i <= tot1; ++i)
{
for (int j = tot1 + 1; j <= tot2; ++j)
{
if (dist(cnt[i][0], cnt[i][1], cnt[j][0], cnt[j][1]) > t) // 花费时间大于t
continue;
addedge(i, j, inf); // 人员与救生设备之间连边，权值为无穷大
}
}
int ans = DINIC();
printf("%d\n", ans);
for (int i = 0; i <= tot2; ++i) // 清空
tab[i].clear();
tab[T].clear();
}
return 0;
}

The end.
2018-08-18 星期六