1340: [Baltic2007]Escape逃跑问题
Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 264 Solved: 121[][][]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
1
HINT
1 <= W <= 50,000 1 <= L <= 50,000 1 <= N <= 250
Source
Solution
最小割裸题....
Code
#include#include #include #include #include #include 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 q;int cur[MAXN],S,T,h[MAXN];#define INF 0x7fffffffbool bfs(){ queue 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\n",Dinic()); return 0;}