方伯伯浇水2 - C++ 代码实现玉米田浇水问题

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

const int N = 100010;

int m;
struct circle
{
    int x, y, r;
}c[N];
int q[N];
bool st[N];
int h[N], e[N], ne[N], idx;
int din[N];
double dist[N];
int cnt[N];
int x[N], y[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++, cnt[b] = c;
}

void topsort()
{
    int hh = 0, tt = -1;
    for (int i = 1; i <= m; i ++ )
        if (!din[i])
            q[ ++ tt] = i;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            cnt[j] += cnt[t];
            dist[j] += dist[t] + cnt[t];
            din[j] -- ;
            if (!din[j])
                q[ ++ tt] = j;
        }
    }
}

int main()
{
    cin >> m;

    memset(h, -1, sizeof h);

    for (int i = 1; i <= m; i ++ )
        cin >> c[i].x >> c[i].y >> c[i].r;

    for (int i = 1; i <= 10; i ++ )
        cin >> x[i] >> y[i];

    for (int i = 1; i <= m; i ++ )
        for (int j = 1; j <= 10; j ++ )
        {
            double d = sqrt((c[i].x - x[j]) * (c[i].x - x[j]) + (c[i].y - y[j]) * (c[i].y - y[j]));
            if (d < c[i].r)
            {
                add(i, j + m, 1);
                din[j + m] ++ ;
            }
        }

    topsort();

    double res = 0;
    for (int i = 1; i <= 10; i ++ )
    {
        int t = i + m;
        if (cnt[t])
            res += dist[t] / cnt[t];
    }

    printf("%.2lf\n", res);
    return 0;
}