企鹅游行问题

解题思路

本题对所有企鹅的跳跃距离进行限制，对每个冰块上企鹅的起跳次数进行限制，问我们所有企鹅能在哪些冰块上会合。

我们现在需要将这个问题转化成流网络，我们可以把跳来跳去的企鹅看作流量，那么整张图就比较好建了。

最开始某些冰块上都有一些企鹅，那么我们就需要从源点向每个冰块连一条边，容量就是该冰块上的企鹅数量，然后汇点就是企鹅跳向的终点，由于能汇聚所有企鹅的终点才是合法的终点，因此终点其实是不固定的，所以我们最后需要枚举一下终点。

对于两个冰块之间如果可以相互跳，我们就让这两个冰块相互之间连边，容量为 $\infty$ 就行。

目前大部分要求都已经满足了，还需要满足每个冰块的起跳限制，冰块作为图中的点，其实就是对点的流量限制，因此可以使用拆点技巧来控制点的流量。

判断原题的可行解和所建图的可行流是否一一对应呢，答案是肯定的，证明也很简单，可以自行证明。

最终如何哪些冰块能用来回合呢，对于每个冰块能否作为合法终点，只需要求一下最大流，如果到达该冰块的流量等于企鹅的总数，即满流，该冰块就是合法终点，按照这个方法依次判断每个冰块即可。

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 210, M = 20410, INF = 0x3f3f3f3f;
const double eps = 1e-8;

int n, S, T;
double d; //企鹅能跳的最远距离
int h[N], e[M], w[M], ne[M], idx; //邻接表
int q[N], dep[N], cur[N]; //队列、层数、当前弧
PII a[N]; //存储所有点的坐标

bool check(int i, int j) //判断两个点是否能相互跳跃
{
    double x = a[i].first - a[j].first, y = a[i].second - a[j].second;
    return x * x + y * y < d * d + eps;
}

void add(int a, int b, int c) //添加边
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
    e[idx] = a, w[idx] = 0, ne[idx] = h[b], h[b] = idx++;
}

bool bfs() //建立分层图，判断是否存在增广路径
{
    int hh = 0, tt = 0;
    q[0] = S;

    memset(dep, 0, sizeof dep);
    dep[S] = 1;

    cur[S] = h[S];

    while(hh <= tt)
    {
        int t = q[hh++];

        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];

            if(!dep[j] && w[i])
            {
                dep[j] = dep[t] + 1;
                cur[j] = h[j];

                if(j == T) return true;

                q[++tt] = j;
            }
        }
    }
    return false;
}

int find(int u, int flow) //统计从 u 往终点能传输的最大流量，上限为 flow
{
    if(u == T) return flow;

    int rest = flow;
    for(int i = cur[u]; i != -1 && rest; i = ne[i])
    {
        cur[u] = i;

        int j = e[i];
        if(dep[j] == dep[u] + 1 && w[i])
        {
            int k = find(j, min(w[i], rest));
            if(!k) dep[j] = 0;

            w[i] -= k;
            w[i ^ 1] += k;
            rest -= k;
        }
    }
    return flow - rest;
}

int dinic() //求最大流
{
    int maxf = 0, flow;
    while(bfs())
        while(flow = find(S, INF)) maxf += flow;
    return maxf;
}

int main()
{
    int cases;
    scanf("%d", &cases);
    while(cases--)
    {
        memset(h, -1, sizeof h); //初始化邻接表
        idx = 0;

        scanf("%d%lf", &n, &d);

        int tot = 0; //记录总人数
        S = 0; //源点
        for(int i = 1; i <= n; i++)
        {
            int x, y, s, t;
            scanf("%d%d%d%d", &x, &y, &s, &t);
            tot += s; //记录总人数

            a[i] = {x, y}; //将每个点的坐标存储起来
            add(S, i, s); //从源点向每个点连一条容量是该点最开始的企鹅数量的边
            add(i, i + n, t); //对点的流量限制，入点向出点连一条容量是起跳次数的边
        }
        for(int i = 1; i <= n; i++) //连点与点之间的边
            for(int j = i + 1; j <= n; j++)
                if(check(i, j)) //如果两个点之间的距离能相互跳跃
                {
                    add(n + i, j, INF); // i 的出边向 j 的入边连一条容量是 INF 的边
                    add(n + j, i, INF); // j 的出边向 i 的入边连一条容量是 INF 的边
                }

        int cnt = 0; //记录合法冰块的数量
        for(int i = 1; i <= n; i++) //枚举每个冰块能否作为终点
        {
            T = i; //将当前冰块作为终点

            for(int j = 0; j < idx; j += 2) //还原整个残量网络
            {
                w[j] += w[j ^ 1]; //把流掉的容量加回来，即加上反向边的容量
                w[j ^ 1] = 0; //将反向边的容量清空
            }

            if(dinic() == tot) //如果当前点的流量等于总人数，说明当前点可以作为终点
            {
                printf("%d ", i - 1); //输出编号（原编号从 0 开始）
                cnt++; //终点数 + 1
            }
        }
        if(!cnt) puts("-1"); //如果没有合法终点，说明无解
        else puts("");
    }
    return 0;
}