HDU 3126 Nova(计算几何+二分+最大流)

Description:

The Lich is a powerful hero that he can kill a wisp with his skill Frost Nova. The Burning Legion wants to conquer the forest so they sent some liches to kill all the wisps. A lich can kill a wisp once he could see the wisp and the wisp in his attack range. So the lich can attack a wisp when the distance between them is less than or equal to specific R and no trees are on the segment between the lich and wisp. Each lich has a cool down time that once he used Frost Nova he has to wait a few seconds for the next attack. Different liches may have different attack range and cool down time. The Lich King is the leader of the Burning Legion and he wants to arrange the attack order so the liches can wipe out all the wisps as soon as possible.

Input:

The first line consists of an integer T, indicating the number of test cases.
The first line of each case consists of three integers N, M, K, indicating the number of lich, the number of wisps and the number of trees. The next N lines, each line consists of four integers x, y, r, t indicating the coordinate of that a lich, the radius of the attack range that lich’s Frost Nova can reach and the value of cool down time. The next M lines, each line consists of two integers x, y indicating the coordinate of each wisp. The last K lines, each line consists of three integers x, y, r, indicating the coordinate and radius of a tree. A lich cannot attack a wisp if the segment between them has a common point with the tree. The lich, wisp and trees will not overlap with each other.

Output:

Output the minimum time lich need to kill all the wisps on a single line, or -1 if lich cannot kill all the wisps.

Constrains
0 < T <= 20
0 <= N, M, K <= 200
-10000 <= x, y <= 10000
0 <= r, t <= 10002

Sample Input:

1
2 3 1
-100 0 100 3
100 0 100 5
-100 -10
100 10
110 11
5 5 10

Sample Output:

题目链接

从平面地图上看有 $n$ 个巫妖 $l i c h s$ ， $m$ 个精灵 $w i s p s$ ， $k$ 棵圆形大树 $t r e e s$

巫妖 $l i c h s_{i}$ 的攻击范围是半径为 $l i c h s_{i} . r$ 的圆，攻击后需要休息 $l i c h s_{i} . t$ 单位时间

若巫妖与精灵之间攻击路线（直线）被大树阻挡则巫妖不可攻击精灵

求巫妖击杀（一次攻击）所有精灵所需的最短时间

首先暴力枚举预处理出每个巫妖可攻击到的所有精灵，之后二分巫妖击杀所有精灵所需的时间，建图用最大流判断二分时间是否合法

建图时将源点与每个巫妖建边流量为 $⌊ \frac{二分时间}{巫妖所需休息时间} ⌋ + 1$ ，将每个巫妖与可攻击精灵建边流量为 $1$ ，将精灵与汇点建边流量为 $1$

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int INF = 0x3f3f3f3f;
const int maxn = 1e3 + 5;
const db eps = 1e-9;

int Sgn(db Key) {return fabs(Key) < eps ? 0 : (Key < 0 ? -1 : 1);}
int Cmp(db Key1, db Key2) {return Sgn(Key1 - Key2);}
struct Point {db X, Y;};
typedef Point Vector;
Vector operator - (Vector Key1, Vector Key2) {return (Vector){Key1.X - Key2.X, Key1.Y - Key2.Y};}
Vector operator + (Vector Key1, Vector Key2) {return (Vector){Key1.X + Key2.X, Key1.Y + Key2.Y};}
db operator * (Vector Key1, Vector Key2) {return Key1.X * Key2.X + Key1.Y * Key2.Y;}
db operator ^ (Vector Key1, Vector Key2) {return Key1.X * Key2.Y - Key1.Y * Key2.X;}
db GetLen(Vector Key) {return sqrt(Key * Key);};
db DisPointToPoint(Point Key1, Point Key2) {return GetLen(Key2 - Key1);}
struct Line {Point S, T;};
typedef Line Segment;
db GetLen(Segment Key) {return GetLen(Key.T - Key.S);}
db DisPointToLine(Point Key1, Line Key2) {return fabs((Key1 - Key2.S) ^ (Key2.T - Key2.S)) / GetLen(Key2);}
db DisPointToSeg(Point Key1, Segment Key2) {
    if (Sgn((Key1 - Key2.S) * (Key2.T - Key2.S)) < 0 || Sgn((Key1 - Key2.T) * (Key2.S - Key2.T)) < 0) {
        return min(DisPointToPoint(Key1, Key2.S), DisPointToPoint(Key1, Key2.T));
    }
    return DisPointToLine(Key1, Key2);
}
struct Circle {Point Center; db Radius;};
bool IsCircleInterSeg(Circle Key1, Segment Key2) {return Cmp(DisPointToSeg(Key1.Center, Key2), Key1.Radius) <= 0;}
struct Lich {Circle Pos; int T;};

struct Edge {int V, Weight, Next;};
Edge edges[100005];
int Head[maxn];
int Tot;
int Depth[maxn];
int Current[maxn];

void GraphInit() {Tot = 0; memset(Head, -1, sizeof(Head));}
void AddEdge(int U, int V, int Weight, int ReverseWeight = 0) {
    edges[Tot] = (Edge){V, Weight, Head[U]};
    Head[U] = Tot++;
    edges[Tot] = (Edge){U, ReverseWeight, Head[V]};
    Head[V] = Tot++;
}

bool Bfs(int Start, int End) {
    memset(Depth, -1, sizeof(Depth));
    std::queue<int> Que;
    Depth[Start] = 0;
    Que.push(Start);
    while (!Que.empty()) {
        int Cur = Que.front();
        Que.pop();
        for (int i = Head[Cur]; ~i; i = edges[i].Next) {
            if (Depth[edges[i].V] == -1 && edges[i].Weight > 0) {
                Depth[edges[i].V] = Depth[Cur] + 1;
                Que.push(edges[i].V);
            }
        }
    }
    return Depth[End] != -1;
}

int Dfs(int Cur, int End, int NowFlow) {
    if (Cur == End || NowFlow == 0) return NowFlow;
    int UsableFlow = 0, FindFlow;
    for (int &i = Current[Cur]; ~i; i = edges[i].Next) {
        if (edges[i].Weight > 0 && Depth[edges[i].V] == Depth[Cur] + 1) {
            FindFlow = Dfs(edges[i].V, End, std::min(NowFlow - UsableFlow, edges[i].Weight));
            if (FindFlow > 0) {
                edges[i].Weight -= FindFlow;
                edges[i ^ 1].Weight += FindFlow;
                UsableFlow += FindFlow;
                if (UsableFlow == NowFlow) return NowFlow;
            }
        }
    }
    if (!UsableFlow) Depth[Cur] = -2;
    return UsableFlow;
}

int Dinic(int Start, int End) {
    int MaxFlow = 0;
    while (Bfs(Start, End)) {
        for (int i = Start; i <= End; ++i) Current[i] = Head[i];
        MaxFlow += Dfs(Start, End, INF);
    }
    return MaxFlow;
}

int T;
int N, M, K;
Lich lichs[maxn];
Point wisps[maxn];
Circle trees[maxn];
vector<int> Link[maxn];
int Max;
int Left, Right;
int Ans;

int main(int argc, char *argv[]) {
    scanf("%d", &T);
    for (int Case = 1; Case <= T; ++Case) {
        scanf("%d%d%d", &N, &M, &K);
        for (int i = 1; i <= N; ++i) scanf("%lf%lf%lf%d", &lichs[i].Pos.Center.X, &lichs[i].Pos.Center.Y, &lichs[i].Pos.Radius, &lichs[i].T);
        for (int i = 1; i <= M; ++i) scanf("%lf%lf", &wisps[i].X, &wisps[i].Y);
        for (int i = 1; i <= K; ++i) scanf("%lf%lf%lf", &trees[i].Center.X, &trees[i].Center.Y, &trees[i].Radius);
        Max = -1;
        for (int i = 1; i <= N; ++i) {
            Max = max(Max, lichs[i].T); Link[i].clear();
            for (int j = 1; j <= M; ++j) {
                if (Cmp(DisPointToPoint(lichs[i].Pos.Center, wisps[j]), lichs[i].Pos.Radius) <= 0) {
                    bool Flag = true;
                    for (int k = 1; k <= K; ++k)
                        if (IsCircleInterSeg(trees[k], (Segment){lichs[i].Pos.Center, wisps[j]})) Flag = false;
                    if (Flag) Link[i].push_back(j);
                }
            }
        }
        Ans = -1; Left = 0; Right = INF;
        while (Left <= Right) {
            int Mid = (Left + Right) >> 1;
            GraphInit();
            for (int i = 1; i <= N; ++i) {
                AddEdge(0, i, Mid / lichs[i].T + 1);
                for (int j = 0; j < (int)Link[i].size(); ++j) AddEdge(i, N + Link[i][j], 1);
            }
            for (int i = 1; i <= M; ++i) AddEdge(N + i, N + M + 1, 1);
            if (Dinic(0, N + M + 1) >= M) {
                Ans = Mid;
                Right = Mid - 1;
            }
            else Left = Mid + 1;
        }
        printf("%d\n", Ans);
    }
    return 0;
}