[BalticOI2007] Escape

· · 题解

原题链接

考虑何时必须消灭士兵才能通过。

可以发现，在最优方案中，要消灭士兵当且仅当若干个士兵的观察范围将峡谷的上边界和下边界连通，我们才消灭其中一个士兵。

明显的最小割模型——割掉最小数量的士兵，使得上边界和下边界不连通，那么就找到了一条通路。

实现细节

峡谷下边界为 s，上边界为 t。

对于每一个圆心 (x_i,y_i)。

若 y_i\leq 100，从 s 向 i 加一条流量为 1 的边。

若 y_i\geq w-100，从 i 向 t 加一条流量为 1 的边。

对于点 (x_j,y_j) 使得 y_j\geq y_i 且 dis(i,j)\leq 200，由 i 向 j 加一条流量为 \inf 的边。

在该图上得到的最大流即为答案。

算距离时最好不要用 double。

Code

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define pow(x) ((x)*(x))
#define mset(arr,val) memset(arr,val,sizeof(arr))
using namespace std;
typedef pair<int,int>pii;
const int SIZE=1010,EXTRA=5e5+10,s=SIZE-2,t=SIZE-1,inf=0x3f3f3f3f;
inline int read()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=(x*10)+(ch^48),ch=getchar();
    return x;
}
queue<int>q;
int l,w,n,dpth[SIZE],head[SIZE],sizee;
struct edge{int u,v,w,nxt;}e[EXTRA];
inline void add(int u,int v,int w){e[sizee]={u,v,w,head[u]},head[u]=sizee++;}
inline void add_edge(int u,int v,int w){add(u,v,w),add(v,u,0);}
pii p[SIZE];
inline bool bfs()
{
    mset(dpth,0),dpth[s]=1,q.push(s);
    while(!q.empty())
    {
        int thisp=q.front();q.pop();
        for(int i=head[thisp];~i;i=e[i].nxt)if(!dpth[e[i].v]&&e[i].w)dpth[e[i].v]=dpth[thisp]+1,q.push(e[i].v);
    }
    return dpth[t];
}
int dfs(int thisp,int rate)
{
    if(thisp==t)return rate;
    int out=0;
    for(int i=head[thisp],_rate;~i;i=e[i].nxt)if(e[i].w&&dpth[e[i].v]==dpth[thisp]+1)
    {
        _rate=dfs(e[i].v,min(rate,e[i].w));
        rate-=_rate,out+=_rate,e[i].w-=_rate,e[i^1].w+=_rate;
        if(!rate)break;
    }
    if(!out)dpth[thisp]=0;
    return out;
}
inline int dinic(){int res=0;while(bfs())res+=dfs(s,inf);return res;}
inline bool cmp(pii x,pii y){return x.second==y.second?x.first<y.first:x.second<y.second;}
inline int dis(pii x,pii y){return pow(x.first-y.first)+pow(x.second-y.second);}
int main()
{
    mset(head,-1);
    l=read(),w=read(),n=read();
    for(int i=1;i<=n;i++)p[i].first=read(),p[i].second=read();
    sort(p+1,p+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(p[i].second<=100)add_edge(s,i,1);
        if(p[i].second>=w-100)add_edge(i,t,1);
        for(int j=i+1;j<=n;j++)
        {
            if(dis(p[i],p[j])<=40000)add_edge(i,j,inf);
        }
    }
    printf("%d",dinic());
    return 0;
}