2019CCPC秦皇岛站-E.Escape(网络流)

题目链接:2019CCPC秦皇岛站-E.Escape

题意:

有一个网格图,上面有一些障碍,然后有a个入口,每个入口会进入一个机器人,机器人最初只会竖直向下走,然后可以放置一些转向装置,可强制机器人转向,问是否所有的机器人都能从出口出来。

题解:

每个格子的水平方向和竖直方向都只能被使用一次,因为两个机器人的路径不可能合并,也不可能迎面相撞。

如果一个格子没有放转弯装置,则可以被水平穿过一次,竖直穿过一次。如果一个格子放了转弯装置,则这个格子只能被一个机器人经过一次。

所以对于所有非障碍格子,可以拆成水平点和竖直点,每个点限流 1(即拆为出点和入点,容量均为1),上下相邻的格子连竖直点(竖直直行),左右相邻的格子连水平点(水平直行),格子内部的水平点和竖直点互相相连(转弯),源连向起点的竖直点,出口的竖直点连向汇,跑最大流,如果最大流 = 机器人个数,则输出 Yes,否则输出 No。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e4 + 10;
const int MAXM = 2e5 + 10;
const int inf = 0x3f3f3f3f;
int T, n, m, bot, ext;
int mp[103][103];
int tot;
struct EDGE
{
    int v, nxt, w;
} edge[MAXM << 1];
int ecnt = 0, fir[MAXN];
void addedge(int u, int v, int w)
{
    edge[ecnt].v = v, edge[ecnt].w = w, edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
    swap(u, v);
    edge[ecnt].v = v, edge[ecnt].w = 0, edge[ecnt].nxt = fir[u];
    fir[u] = ecnt++;
}
int cur[MAXN], depth[MAXN];
int dfs(int u, int flow, int st, int ed)
{
    if (u == ed)
        return flow;
    for (int &i = cur[u]; i != -1; i = edge[i].nxt)
    {
        int v = edge[i].v;
        int w = edge[i].w;
        if (depth[v] == depth[u] + 1 && w)
        {
            int di = dfs(v, min(flow, w), st, ed);
            if (di > 0)
            {
                edge[i].w -= di;
                edge[i ^ 1].w += di;
                return di;
            }
        }
    }
    return 0;
}
bool bfs(int st, int ed)
{
    queue<int> q;
    while (!q.empty())
        q.pop();
    memset(depth, 0, sizeof(depth));
    depth[st] = 1;
    q.push(st);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = fir[u]; i != -1; i = edge[i].nxt)
        {
            int v = edge[i].v;
            int w = edge[i].w;
            if (depth[v] == 0 && w > 0)
            {
                depth[v] = depth[u] + 1;
                q.push(v);
            }
        }
    }
    return depth[ed] > 0;
}
int dinic(int st, int ed)
{
    int sum = 0;
    while (bfs(st, ed))
    {
        for (int i = 0; i <= n * m * 4 + 1; i++)
            cur[i] = fir[i];
        while (int temp = dfs(st, inf, st, ed))
            sum += temp;
    }
    return sum;
}
int getid(int x, int y, int id)
{
    return id * n * m + (x - 1) * m + y;
}
/*
0 横点 入点
1 横点 出点
2 竖点 入点
3 竖点 出点
*/
int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d%d%d", &n, &m, &bot, &ext);
        memset(fir, -1, sizeof(fir));
        ecnt = tot = 0;
        for (int i = 1; i <= n; i++)
        {
            char str[103];
            scanf("%s", str + 1);
            for (int j = 1; j <= m; j++)
            {
                mp[i][j] = str[j] - '0';
                if (mp[i][j])
                    continue;
                addedge(getid(i, j, 0), getid(i, j, 1), 1);
                addedge(getid(i, j, 1), getid(i, j, 2), 1);
                addedge(getid(i, j, 2), getid(i, j, 3), 1);
                addedge(getid(i, j, 3), getid(i, j, 0), 1);
            }
        }

        for (int i = 1; i <= n - 1; i++)
            for (int j = 1; j <= m; j++)
                if (!mp[i][j] && !mp[i + 1][j])
                    addedge(getid(i, j, 3), getid(i + 1, j, 2), 1);
        for (int i = 2; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (!mp[i][j] && !mp[i - 1][j])
                    addedge(getid(i, j, 3), getid(i - 1, j, 2), 1);

        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m - 1; j++)
                if (!mp[i][j] && !mp[i][j + 1])
                    addedge(getid(i, j, 1), getid(i, j + 1, 0), 1);
        for (int i = 1; i <= n; i++)
            for (int j = 2; j <= m; j++)
                if (!mp[i][j] && !mp[i][j - 1])
                    addedge(getid(i, j, 1), getid(i, j - 1, 0), 1);
        for (int i = 1; i <= bot; i++)
        {
            int x;
            scanf("%d", &x);
            addedge(0, getid(1, x, 2), 1);
        }
        for (int i = 1; i <= ext; i++)
        {
            int x;
            scanf("%d", &x);
            addedge(getid(n, x, 3), n * m * 4 + 1, 1);
        }
        dinic(0, n * m * 4 + 1) == bot ? puts("Yes") : puts("No");
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。