R的农场 chebnear

　　评测传送门

Description
最近,R 终于获得了一片他梦寐以求的农场,但如此大的一片农场,想要做好防卫工作可不是一件容易的事。所以 R 购买了 N 个守卫,分别让他们站在一定的位置上(守卫不可移动,同一位置上至多有一个守卫)。但是,安排了所有的守卫之后,R 才发现,守卫们彼此十分厌恶。经 R 研究,当某两个守卫距离≤K,他们就会发生争吵;但是,想要守卫们和解也是不难的——只需要 R 给出的平均工资能使两人满意,他们就会同意和解、成为朋友;当然,如果两个守卫有共同的朋友,他们也会和解成为朋友。R 非常不想守卫们争吵,因此他想找出,在能使所有守卫闭嘴的前提下,平均工资的最小值是多少。

他想到了一个绝妙的方法,但他忙着去 Farm,没时间,所以这个任务就交给你了。
Input
第 1 行为三个数 N, M, K。
接下来 N 行为 N 个守卫的位置,每行包含两个实数 x, y (x≥0, y≥0)。
接下来 M 行,每行三个数,u, v, w,代表若平均工资≥w,则 u 和 v 同意和解。
Output
输出文件有且仅有一行,一个实数 p,代表最小的平均工资。

data range

M≤100000, M≤200000

Attention
1、本题中的距离定义:对于两个守卫 (x1, y1), (x2, y2) ,它们的距离定义为 max{|x1-x2|,|y1-y2|} 。
2、整数均在 int 范围内,实数均在 double 范围内。
3、给定图中可能存在重边。
4、输出结果保留三位小数。

25分思路：

　　预处理出发生冲突的守卫编号

　　然后依据输入的两个守卫成为friends的最低平均工资连边

　　边权即为输入的最低工资

　　然后枚举之前预处理出的发生冲突的守卫　求出它们之间的最短路

　　这里路长的定义为：经过的所有路径的边权的最大值，而不是所有路径边权相加

　　在所有的最短路之间取max即可

正解思路：

　　枚举最低平均工资

　　发现它可以二分即若当前最低平均工资满足所有守卫无冲突

　　则 r=mid-1寻找更小的反之....

　　二分工资之后怎么判断是否符合题意呢：

　　若两个守卫成为朋友的最低工资<=mid 那么连边(用并查集就可以了)

　　然后求平面内最近点对(连了线的两点不对答案做贡献) (这里是最近点对qwq)

　　若最近点对之间的距离>k则合题意

我觉得上面辣种求最近点对的思路很好但是我调了很久的code还没好

然后又借鉴了一下wch的想法我发现也很好啊不用求最近点对了

也是分治找有没有两点之间的距离小于等于k 直接在solve里面判断

CODE：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cmath>

 #define R register

 #define go(i,a,b) for(R int i=a;i<=b;i++)

 #define M 100001

 #define db double

 #define inf 210000000.0

 using namespace std;

 struct node1{db x,y;int id;}a[M],c[M];

 struct node2{int u,v;db w;}b[M<<];

 int n,m,f[M];

 db k;

 int find(int x){if(f[x]==x)return x;return f[x]=find(f[x]);}

 bool cmp1(node2 x,node2 y){return x.w<y.w;}

 bool cmp2(node1 x,node1 y){return x.y<y.y;}

 bool cmp3(node1 x,node1 y){return x.x<y.x;}

 bool sol(int l,int r)

 {

     if(l>=r) return ;//边界

     int mid=(l+r)>>,ct=;

     if(!sol(l,mid)||!sol(mid+,r)) return ;

     while(a[l].x+k<a[mid].x) l++;

     while(a[r].x-k>a[mid].x) r--;

     go(i,l,r) c[++ct]=a[i];

     sort(c+,c+ct+,cmp2);

     go(i,,ct)

         go(j,i+,ct)

     {

         if(c[j].y-c[i].y>k) break;

         if(fabs(c[i].x-c[j].x)<=k&&find(c[i].id)!=find(c[j].id)) return ;

         //这里只要判断x 因为已经保证 c[j].y-c[i].y<=k

     }

     return ;

 }

 bool ck(int mid)

 {

     go(i,,n) f[i]=i; //不要落掉这一步啦 写并查集的时候一定要记得！

     go(i,,m)

     {

         if(b[i].w>b[mid].w) break;

         f[find(b[i].u)]=find(b[i].v);//注意这里啊 开始写错了找了好久qwq

     }

     return sol(,n);

 }

 int main()

 {

     cin>>n>>m>>k;

     go(i,,n) cin>>a[i].x>>a[i].y,a[i].id=i;

     sort(a+,a+n+,cmp3);//按x排序

     go(i,,m) cin>>b[i].u>>b[i].v>>b[i].w;

     sort(b+,b+m+,cmp1);//按w排序

     //好像很少写对过二分？？初始化 mid+-1什么的总是搞错

     //然后这题的二分还不清楚为什么我之前写的不对 要去问一下 然后再写到这里来

     int l=,r=m-,mid;//这里要注意l,r的初始化

     while(l<=r)

     {

         mid=(l+r)>>;

         if(ck(mid)) {r=mid-;}

         else l=mid+;

     }

     printf("%.3lf",b[l].w);

     return ;

 }

巴特西

R的农场 chebnear

最新文章

热门文章