UVA12125 题解

yyrwlj · 2024-01-28 11:24:18 · 题解

题意简述

有 n 个点，每个点最开始有 n_i 头猪，每个点最多能被经过 m_i 次，若两点的距离不超过 D，则两点互相可达。

输出哪些点可以让所有的猪运到这个点，若没有输出 -1。

思路

考虑使用网络最大流求解。

每个点最开始有 n_i 头猪，很显然要从源点 S 向 i 连一条容量为 n_i 的边。

每个点最多能被经过 m_i 次，不难想到拆点，入点向出点连一条容量为 m_i 的边。

其余连边直接使用距离公式，若距离小于等于 D，则互相从自己的出点向对方的入点连一条容量为 +\infty 的边

然后枚举每个点当汇点，若最大流量等于猪的总数，则当前点可以让所有猪运到这个点。

记得多测要清空。

Code

#define x first
#define y second
using namespace std;
const int N = 205, M = (600 + 200 * 199) * 2, inf = 1e8;
const double eps = 1e-8;
struct Edge{
    int e, to, nxt;
}g[M];
int h[N], idx = 1;
int dep[N], now[N], q[N];
pair<int, int> p[N];
int S, T;
void add(int a,int b,int c)
{
    g[++idx] = {c, b, h[a]}, h[a] = idx;
    g[++idx] = {0, a, h[b]}, h[b] = idx;
}
inline double dist(int i,int j)
{
    return sqrt((p[i].x - p[j].x) * (p[i].x - p[j].x) + (p[i].y - p[j].y) * (p[i].y - p[j].y));
}
bool bfs()
{
    memset(dep, 0, sizeof dep);
    dep[S] = 1;
    int hh = 0, tt = 0;
    q[0] = S;
    now[S] = h[S];
    while (hh <= tt)
    {
        int t = q[hh ++];
        for (int i = h[t]; i; i = g[i].nxt)
        {
            int j = g[i].to;
            if (dep[j] || !g[i].e)
                continue;
            dep[j] = dep[t] + 1;
            now[j] = h[j];
            if (j == T)
                return true;
            q[++ tt] = j;
        }
    }
    return false;
}
int find(int u,int lim)
{
    if (u == T)
        return lim;
    int flow = 0;
    for (int i = now[u]; i && flow < lim; i = g[i].nxt)
    {
        now[u] = i;
        int j = g[i].to;
        if (dep[j] != dep[u] + 1 || !g[i].e)
            continue;
        int v = find(j, min(g[i].e, lim - flow));
        if (!v)
            dep[j] = 0;
        else
        {
            g[i].e -= v;
            g[i ^ 1].e += v;
            flow += v;
        }
    }
    return flow;
}
int dinic()
{
    int res = 0, flow;
    while (bfs())
        while (flow = find(S, inf))
            res += flow;
    return res;
}
void work()
{
    memset(h, 0, sizeof h);
    idx = 1;
    int n, sum = 0;
    double D;
    scanf("%d%lf", &n, &D);
    for (int i=1;i<=n;i++)
    {
        int x, y, a, b;
        scanf("%d%d%d%d", &x, &y, &a, &b);
        p[i] = {x, y};
        add(S, i, a);
        add(i, i + n, b);
        sum += a;
    }
    for (int i=1;i<n;i++)
        for (int j=i+1;j<=n;j++)
            if (D - dist(i, j) > eps)
            {
                add(i + n, j, inf);
                add(j + n, i, inf);
            }
    bool no = true;
    for (int i=1;i<=n;i++)
    {
        for (int j=2;j<=idx;j+=2)
        {
            g[j].e += g[j ^ 1].e;
            g[j ^ 1].e = 0;
        }
        T = i;
        if (dinic() == sum)
        {
            no = false;
            printf("%d ", i - 1);
        }
    }
    if (no)
        puts("-1");
    else
        putchar('\n');
}

不建议直接复制代码提交。