【BZOJ-1340】Escape逃跑问题最小割

1340: [Baltic2007]Escape逃跑问题

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 264 Solved: 121
[Submit][Status][Discuss]

Description

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

Input

第一行有三个整数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不一定是整数。

Output

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

Sample Input

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

Sample Output

HINT

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

Source

Solution

最小割裸题....

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f; 
}
#define MAXN 1010
#define MAXM 1001010 
int L,W,N;
struct PointNode{int x,y;}P[MAXN];
struct EdgeNode{int next,to,cap;}edge[MAXM];
int head[MAXN],cnt=1;
void AddEdge(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=w;}
void InsertEdge(int u,int v,int w) {AddEdge(u,v,w); AddEdge(v,u,0);}
queue<int>q;
int cur[MAXN],S,T,h[MAXN];
#define INF 0x7fffffff
bool bfs()
{
    queue<int>q;
    for (int i=S; i<=T; i++) h[i]=-1;
    h[S]=1; q.push(S);
    while (!q.empty())
        {
            int now=q.front(); q.pop();
            for (int i=head[now]; i; i=edge[i].next)
                if (h[edge[i].to]==-1 && edge[i].cap)
                    h[edge[i].to]=h[now]+1,q.push(edge[i].to);
        }
    return h[T]!=-1;        
}
int dfs(int loc,int low)
{
    if (loc==T) return low;
    int used=0,w;
    for (int i=cur[loc]; i; i=edge[i].next)
        if (edge[i].cap && h[edge[i].to]==h[loc]+1)
            {
                w=dfs(edge[i].to,min(edge[i].cap,low-used));
                edge[i].cap-=w; edge[i^1].cap+=w; used+=w;
                if (used==low) return low;
                if (edge[i].to) cur[loc]=i;
            }
    if (!used) h[loc]=-1;
    return used;
}
int Dinic()
{
    int tmp=0;
    while (bfs())
        {
            for (int i=S; i<=T; i++) cur[i]=head[i];
            tmp+=dfs(S,INF);
        }
    return tmp;
}
int Dis(PointNode a,PointNode b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
int main()
{
    L=read(),W=read(),N=read();
    for (int x,y,i=1; i<=N; i++) P[i].x=read(),P[i].y=read();
    S=0,T=2*N+1;
    for (int i=1; i<=N; i++)
        for (int j=1; j<=N; j++)
            if (Dis(P[i],P[j])<=200 && i!=j) InsertEdge(i+N,j,INF);
    for (int i=1; i<=N; i++)
        {
            if (P[i].y<=100) InsertEdge(S,i,INF);
            if (abs(W-P[i].y)<=100) InsertEdge(i+N,T,INF);
            InsertEdge(i,i+N,1);
        }
    printf("%d
",Dinic());
    return 0;
}