战犯们企图逃离*，他们详细地计划了如何逃出*本身，逃出*之后他们希望在附近的一个村子里找到掩护。村子（下图中的B）和*（图中的A）中间有一个峡谷，这个峡谷也是有士兵守卫的。守卫峡谷的士兵们坐在岗哨上很少走动，每个士兵的观察范围是100米。士兵所处位置决定了战犯们能否安全通过峡谷，安全通过的条件就是在任何时刻战犯们距离最近的士兵大于100米。 给定峡谷的长、宽和每个士兵在峡谷中的坐标，假定士兵的位置一直保持不变，请你写一个程序计算战犯们能否不被士兵发现，顺利通过峡谷。如果不能，那么战犯们最少需要消灭几个士兵才能安全通过峡谷（无论士兵是否被另一个士兵看到，他都可以被消灭）。 

 

 

第一行有三个整数L、W和N，分别表示峡谷的长度、宽度和士兵的人数。接下来的N行，每行两个整数Xi和Yi，表示第i个士兵在峡谷的坐标（0 <= Xi <= L, 0 <= Yi <= W)，坐标以米为单位，峡谷的西南角坐标为(0, 0)，东北角坐标为(L, W)，见上图。注意：通过峡谷可以从(0, ys)（0 <= ys <= W）到（L, ye）（0 <= ye <= W），其中ys， ye不一定是整数。

只有一行，为一个整数，即安全通过峡谷需要消灭的士兵的人数，如果不需要消灭任何士兵，则输出0。

130 340 5
10 50
130 130
70 170
0 180
60 260

1

1 <= W <= 50,000 1 <= L <= 50,000 1 <= N <= 250

 

 #include <bits/stdc++.h>

 const int siz = ;

 const int inf = ;

 int L, W, N;

 int X[siz];

 int Y[siz];

 int S, T;

 int hd[siz];

 int nt[siz];

 int to[siz];

 int fl[siz];

 inline void add(int u, int v, int f)

 {

     static int edge = , init = ;

     if (init)memset(hd, -, sizeof(hd)), init = ;

     nt[edge] = hd[u]; to[edge] = v; fl[edge] = f; hd[u] = edge++;

     nt[edge] = hd[v]; to[edge] = u; fl[edge] = ; hd[v] = edge++;

 }

 int dep[siz];

 inline bool bfs(void)

 {

     static int que[siz], l, r;

     memset(dep, , sizeof(dep));

     dep[que[l = ] = S] = r = ;

     while (l != r)

     {

         int u = que[l++], v;

         for (int i = hd[u]; ~i; i = nt[i])

             if (fl[i] && !dep[v = to[i]])

                 dep[que[r++] = v] = dep[u] + ;

     }

     return dep[T];

 }

 int cur[siz];

 int dfs(int u, int f)

 {

     using std::min;

     if (u == T || !f)

         return f;

     int used = , flow, v;

     for (int i = cur[u]; ~i; i = nt[i])

         if (fl[i] && dep[v = to[i]] == dep[u] + )

         {

             flow = dfs(v, min(fl[i], f - used));

             used += flow;

             fl[i] -= flow;

             fl[i^] += flow;

             if (fl[i])

                 cur[u] = i;

             if (f == used)

                 return f;

         }

     if (!used)

         dep[u] = ;

     return used;

 }

 inline int maxFlow(void)

 {

     int maxFlow = , newFlow;

     while (bfs())

     {

         memcpy(cur, hd, sizeof(cur));

         while (newFlow = dfs(S, inf))

             maxFlow += newFlow;

     }

     return maxFlow;

 }

 inline long long sqr(long long x)

 {

     return x * x;

 }

 inline long long dis(int i, int j)

 {

     return sqr(X[i] - X[j]) + sqr(Y[i] - Y[j]);

 }

 signed main(void)

 {

     scanf("%d%d%d", &L, &W, &N);

     for (int i = ; i <= N; ++i)

         scanf("%d%d", X + i, Y + i);

     S = , T =  * N + ;

     for (int i = ; i <= N; ++i)

     {

         add(i, i + N, );

         if (Y[i] <= )add(S, i, inf);

         if (Y[i] >= W - )add(i + N, T, inf);

     }

     for (int i = ; i <= N; ++i)

         for (int j = ; j <= N; ++j)

             if (dis(i, j) <=  && i != j)

                 add(i + N, j, inf);

     printf("%d\n", maxFlow());

 }