自动搬运

查看原文

来自洛谷，原作者为

	FQ04gty Let me be cruel, not unnatural.

搬运于2025-08-24 22:17:11，当前版本为作者最后更新于2022-10-19 21:38:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题链接

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

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

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

实现细节

峡谷下边界为 $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;
}