首页 > 代码库 > bzoj 1390: [Ceoi2008]Fence
bzoj 1390: [Ceoi2008]Fence
Description
在一个大小为1000*1000的区域中，有n个固定点,m棵tree 。 现在你要建一个围栏来保护tree,建它的费用为你选用的固定点的个数 *20和 你没有圈进围栏的tree*111. 现在希望这个值越小越好. 3<=N<=100. 1<=M<=100
Input
第一行给出n,m 下面开始n行，给出固定的坐标 下面开始m行，给出tree的坐标
Output
输出最小费用
根据题目设定的参数，凡是可以围住的点都要围住，同bzoj1027可以转为最小环
#include<bits/stdc++.h>struct pos{ int x,y; void read(){ scanf("%d%d",&x,&y); }}ns[107],ms[107],cs[107];pos operator-(pos a,pos b){return (pos){a.x-b.x,a.y-b.y};}int operator*(pos a,pos b){return a.x*b.y-a.y*b.x;}bool operator<(pos a,pos b){return a*b<0;}int ans=0,n,m,cp=0;bool in(pos w){ for(int i=2;i<cp;++i)if(cs[i-1]<w&&w<cs[i]){ return cs[i-1]-w<cs[i]-w; } return 0;}void mins(int&a,int b){if(a>b)a=b;}int l[107][107];char s[107][107];int main(){ scanf("%d%d",&n,&m); for(int i=0;i<n;++i)ns[i].read(); for(int i=0;i<m;++i)ms[i].read(); for(int i=1;i<n;++i)if(ns[i].x<ns[0].x)std::swap(ns[i],ns[0]); pos p0=ns[0]; for(int i=0;i<n;++i)ns[i]=ns[i]-p0; for(int i=0;i<m;++i)ms[i]=ms[i]-p0; std::sort(ns+1,ns+n); for(int i=0;i<n;++i){ while(cp>=2&&ns[i]-cs[cp-1]<cs[cp-1]-cs[cp-2])--cp; cs[cp++]=ns[i]; } int p=0; for(int i=0;i<m;++i){ if(!in(ms[i]))ans+=111; else ms[p++]=ms[i]; } m=p; if(p){ for(int i=0;i<n;++i){ for(int j=0;j<n;++j){ l[i][j]=0x3f3f3f3f; if(i!=j){ bool is=1; pos d=ns[i]-ns[j]; for(int k=0;k<m;++k)if(d<ms[k]-ns[j]){ is=0; break; } if(is)l[i][j]=1; } } } for(int k=0;k<n;++k) for(int i=0;i<n;++i) for(int j=0;j<n;++j)mins(l[i][j],l[i][k]+l[k][j]); for(int i=1;i<n;++i)mins(l[0][0],l[i][i]); ans+=l[0][0]*20; } printf("%d\n",ans); return 0;}
bzoj 1390: [Ceoi2008]Fence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。