首页 > 代码库 > bzoj1340: [Baltic2007]Escape逃跑问题
bzoj1340: [Baltic2007]Escape逃跑问题
题意:http://www.lydsy.com/JudgeOnline/problem.php?id=1340
挺好的一道题...
有曲线不能从左下到右上等价于,不存在从左上到右下的曲线,满足曲线一直在圆内或矩形边界上
所以删除数量最小的圆,使得上下不连通即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define rep(i,l,r) for(int i=l;i<=r;++i) 4 const int N=202333,inf=2147483647; 5 int head[N],n,m,dis[N],tot=1,sum,T,K; 6 struct node{ 7 int x,y; 8 }s[N]; 9 struct zs{ 10 int to,next,w; 11 }e[N]; 12 inline void ins(int u,int v,int w){ 13 e[++tot].to=v; e[tot].next=head[u]; head[u]=tot; e[tot].w=w; 14 } 15 inline void insert(int u,int v,int w){ 16 ins(u,v,w); ins(v,u,0); 17 } 18 inline bool bfs(){ 19 rep(i,0,T) dis[i]=-1; queue<int>q; q.push(0); dis[0]=0; 20 while(!q.empty()) { 21 int x=q.front(); q.pop(); 22 for(int k=head[x];k;k=e[k].next) 23 if(dis[e[k].to]<0 && e[k].w>0) { 24 dis[e[k].to]=dis[x]+1; q.push(e[k].to); 25 } 26 } 27 if(dis[T]>0) return 1;else return 0; 28 } 29 int find(int x,int low){ 30 if(x==T) return low; 31 int delta=low,now; 32 for(int k=head[x];k;k=e[k].next) 33 if(e[k].w>0 && dis[e[k].to]==dis[x]+1){ 34 now=find(e[k].to,min(e[k].w,delta)); 35 e[k].w-=now; e[k^1].w+=now; delta-=now; 36 if(!delta) return low; 37 } 38 dis[x]=-1; 39 return low-delta; 40 } 41 int main(){ 42 scanf("%d%d%d",&n,&m,&K); 43 T=K*2+1; 44 rep(i,1,K) { 45 scanf("%d%d",&s[i].x,&s[i].y); 46 if(s[i].y<=100) insert(0,i,inf); 47 if(abs(s[i].y-m)<=100) insert(i+K,T,inf); 48 insert(i,i+K,1); 49 } 50 rep(i,1,K) rep(j,1,K) if(i!=j&&(s[i].x-s[j].x)*(s[i].x-s[j].x)+(s[i].y-s[j].y)*(s[i].y-s[j].y)<=200*200) 51 insert(i+K,j,inf); 52 while(bfs()) sum+=find(0,inf); 53 printf("%d\n",sum); 54 }
bzoj1340: [Baltic2007]Escape逃跑问题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。