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

Sample Output

Problem Source

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

链接

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

题意

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

题解

多源点多汇点问题，需要注意，每个区域可能有多个人和多个救生设备。最开始是想用二分图匹配来做，将一个区域内的所有人/救生设备都拆成点，然后在t分钟内可以到达的就连边，再跑一个二分图最大匹配。但是，超时了！！！因为最多可能会出现900个人，900个救生设备，边数也会相当庞大，时间复杂度$O(VE)$。
后面尝试着转化为网络流，不拆点，人与超级源连边，救生设备与超级汇连边，边权分别为一个区域内人/救生设备的数量，人与可以在t分钟内到达的救生设备去连边，跑一遍最大流（DINIC），然后就过了。这时候点数最多只有202(100+100+1+1)。

代码

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 星期六