BNUOJ 12887 isumi(计算几何+最大流)

Description:

isumi是个斐波那契数迷。他是如此的酷爱这个数列，因此他想知道很多关于这个数列的东西，比方说第N个斐波那契数是多少啊、前N项的和是多少啊如何用若干个斐波那契数的和表示一个自然数啊之类之类的。

今天他希望能想出一个有关斐波那契数的问题能难倒易牛。当然，这需要想相当长的时间，他想到该去吃饭了依然没想出题来，因此他决定边去吃饭边想。isumi的宿舍到食堂之间的路可以看做一个矩形，宿舍在x=0的线的左边，食堂在x=l的线的右边。isumi可以从x=0上的任意一个点出发，只要到达x=l的任意一个点就可以，不过在走的时候不能走出路、也就是矩形的外面，不然正在思考问题的isumi说不定会撞上电线杆- -||

isumi用望远镜观察到在路上有N只大牛(编号为0,1,…N-1)，第i只大牛所在的位置为(xi,yi)(大牛们不会移动，并且每只大牛都在路、也就是矩形之内)，根据isumi对这些大牛的了解，只要isumi出现在某只大牛的视线范围之内这只大牛就会冲过来问isumi一道神题来虐他，虐完之后该大牛就会心满意足的离开……每只大牛的视力不同，当isumi距离第i只大牛不超过di时就会被这只大牛发现。

现在isumi希望知道他至少要被几只大牛发现才能到达食堂。

Input:

第一行为三个整数l,w,N(0<l, w≤10000, 1≤N≤100)，接下来的N行每行三个整数xi,yi,di(0<xi<l, 0<yi<w, 0≤di≤1000)。

Output:

输出一个整数表示isumi至少要被几只大牛发现才能到达食堂。

Sample Input:

500 300 5
250 1 75
250 150 75
250 299 100
100 150 80
400 150 20

Sample Output:

题目链接

如图，若 $向要从左边的宿舍走到右边的食堂则它需要横向穿过矩形区域$

考虑在矩形上面设立源点，矩形下面设立汇点根据圆与矩形边界的相交关系、圆与圆的相交关系建图

在途中很显然的可以看出若 $想要最少地被大牛发现横向穿过矩形区域则他必须穿过建图关系中最少的边$

这样问题就转化为网络流中的最小割问题，又因为最大流最小割定理所以求出建图关系中的最大流即为答案

AC代码:

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const int INF = 0x3f3f3f3f;
const int maxn = 1e4 + 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;
struct Circle {Point Center; db Radius;};
bool IsCircleInterCircle(Circle Key1, Circle Key2) {return Cmp(DisPointToPoint(Key1.Center, Key2.Center), Key1.Radius + Key2.Radius) <= 0;}

struct Edge {int V, Weight, Next;};

Edge edges[maxn << 4];
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;
}

bool CheckCircle(Circle Key1, db Key2) {
    return Cmp(Key1.Center.Y - Key1.Radius, Key2) <= 0 && Cmp(Key1.Center.Y + Key1.Radius, Key2) >= 0;
}

db L, W;
int N;
Circle Daniel[maxn];

int main(int argc, char *argv[]) {
    scanf("%lf%lf%d", &L, &W, &N);
    for (int i = 1; i <= N; ++i) scanf("%lf%lf%lf", &Daniel[i].Center.X, &Daniel[i].Center.Y, &Daniel[i].Radius);
    GraphInit();
    for (int i = 1; i <= N; ++i) AddEdge(i, N + i, 1);
    for (int i = 1; i <= N; ++i) {
        if (CheckCircle(Daniel[i], 0)) AddEdge(0, i, INF);
        if (CheckCircle(Daniel[i], W)) AddEdge(N + i, 2 * N + 1, INF);
    }
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            if (IsCircleInterCircle(Daniel[i], Daniel[j])) {
                AddEdge(N + i, j, INF);
                AddEdge(N + j, i, INF);
            }
        }
    }
    printf("%d\n", Dinic(0, 2 * N + 1));
    return 0;
}