Description

戰犯們企圖逃離監獄，他們詳細地計劃了如何逃出監獄本身，逃出監獄之后他們希望在附近的一個村子里找到掩護。村子和監 獄中間有一個峽谷，這個峽谷也是有士兵守衛的。守衛峽谷的士兵們坐在崗哨上很少走動，每個士兵的觀察范圍是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 1700 180 60 260

Sample Output

1

Hint

【數據范圍】
1≤W≤50000
1≤L≤50000
1≤N≤250 經典的點限制網絡流。首先建圖，將每一個士兵拆成兩個點，并且容量為1。接著判斷兩個士兵之間距離是否小于200(一個人范 圍100，兩個間隔就是200了。。。），如果有連接，就將其連上無向邊，容量為oo。同時，我們的士兵如果和山谷的邊界距離小于 100，則將其連接上邊界代表的源點和匯點。最后簡單的SAP一遍最大流就好了，最大即為最小割，也就是需要擊斃的士兵人數。 蒟蒻的代碼因為用了一種詭異的無向邊添加方式，所以需要8*n*n的空間。。。#include<iostream> #include<cstring> #include<cstdio> using namespace std; int N,W,L,n; const int inf=0x3f3f3f3f; struct Pipe{int next,to,flow;}pipe[500005]; struct psn{int x,y;}psn[2550];//士兵坐標 int h[50005],cnt=1; int Gap[50005],dis[50005]; int ans=0; inline void add(int x,int y,int z){pipe[++cnt].to=y;pipe[cnt].next=h[x];h[x]=cnt;pipe[cnt].flow=z;pipe[++cnt].to=x;pipe[cnt].next=h[y];h[y]=cnt;pipe[cnt].flow=0;return ; }//雙向加邊 inline int read(){char c;int rec=0;while((c=getchar())<'0'||c>'9');while(c>='0'&&c<='9')rec=rec*10+c-'0',c=getchar();return rec; } inline bool cal(int x,int y){int dis=(psn[x].x-psn[y].x)*(psn[x].x-psn[y].x)+(psn[x].y-psn[y].y)*(psn[x].y-psn[y].y);if(dis<=40000)return 1;return 0; }//用整型計算距離，避免浮點型的精度誤差（雖然本來就不多） inline int SAP(int v,int maxflow){if(v==2*N+1)return maxflow;int temp=maxflow,i,j,p;for(i=h[v];i;i=pipe[i].next){j=pipe[i].to;if(pipe[i].flow&&dis[v]==dis[j]+1){p=SAP(j,min(pipe[i].flow,temp));temp-=p;pipe[i].flow-=p;pipe[i^1].flow+=p;if(temp==0||dis[0]==n)return maxflow-temp;}}if(--Gap[dis[v]]==0)dis[0]=n;else Gap[++dis[v]]++;return maxflow-temp; } int main(){L=read();W=read();N=read();int i,j,k;for(i=1;i<=N;i++){psn[i].x=read();psn[i].y=read();add(i,i+N,1);//拆點 if(psn[i].y<=100)add(0,i,inf);//起始源點 if(psn[i].y+100>=W)add(i+N,2*N+1,inf);//結束匯點 }n=N*2+2;//總點數 for(i=1;i<=N;i++)for(j=i+1;j<=N;j++)if(cal(i,j))add(i+N,j,inf),add(j+N,i,inf);//極大浪費空間的雙向加邊 Gap[0]=n;while(dis[0]<n)ans+=SAP(0,inf);//累加得到最大流，即最小割 cout<<ans;//若可以直接穿過山谷，則不存在S-T的線路，則最大流必定為0，無需dfs特判 return 0; }

總結

以上是生活随笔為你收集整理的【BOI2007】逃跑问题 （BSOI2344）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。