[1007]倍杀测量者 题解

2024-01-18 14:22:40

【题目大意】

某地的机房要集体女装，但是教练不想让他们女装，放松了限制，但出题人想至少要有一个人女装，求减去的最大限制使得至少有一个人女装。

咳咳，下面才是正题：

【解题思路】

1 . 总体思路

因为题目中说出了 不小于 ，说明要列不等式，可要用差分约束来解决。

本题要求出最大值 \(T\) 来满足有人女装，直接求 \(T\) 肯定不好求，又因为要求出最大值，考虑二分来解决。

根据题目要求列出不等式，每次分出一个 \(T\) 值，根据这个 \(T\) 值进行连边，跑一遍最长路，如果存在环路就说明合法，可以增加减去的 \(T\) 值，反之减少，最后得出答案。

2 . 条件分析

根据题目，有两种情况 ：

  • 我没 \(k\) 倍杀选手 \(X\)，我就女装
  • 选手 \(Y\) 把我 \(k\) 倍杀我就女装
    所以在教练更改以后同学 \(A\) 要女装的条件分别为 :

\[A < B \times (k - T) \\ A < B \times \frac{1}{(k + T)} \]

根据上面两个式子可以根据差分约束来连边。

  • 第一种情况从 \(B\) 向 \(A\) 连一条边权为 \(k - T\) 的边。
  • 第二种情况从 \(B\) 向 \(A\) 连一条边权为 $ \dfrac{1}{k + T}$ 的边。

要保证图联通，所以建立一个超级源点 \(0\) ，要保证根据已有同学的成绩来作为判断的条件，所以要根据已有同学的成绩连边，连边时注意要两种情况都连边。

例如当知道 \(C\) 的成绩为 \(10\) 时，从 \(0\) 向 \(C\) 建立一条边权为 \(10\) 的边。还要从 \(C\) 向 \(0\) 建立一条边权为 \(\dfrac{1}{10}\) 的边。

这时候基本上都分析完了， 开始二分建图求最大 \(T\)。

3 . 二分建图

二分不用说了吧... 注意精度开大点即可。

4 . 我的错误

被 \(n\) 个错误卡炸的我决定诉说一下

  • 写二分精度的时候 \(EPS\) 要定义为 \(double\) ，否则一直死循环。
  • 因为是乘积最短路，\(dis\) 数组要附初值为 \(1\)；
  • 千万别用 \(memset\) 附初值为 \(1\)，就我傻傻的调了半天也没看出来。
  • 多组数据记着清空；

这些错误也就卡了我半天...

【Code】

/*
By : Ti_Despairy
Time : 2021,1,21;
思路 ：
知识点 ：
*/
#include<cstdio>
#include<queue>
#include<iostream>
#include<cstring>
#define M 1000010
#define N 1010
#define qaq cout<<"可行QAQ"<<endl
#define INF 0x3f3f3f3f
using namespace std;
const int mod1 = 19260817;
const int mod2 = 19660813;
const double EPS = 1e-7;//确保精度 
/*================================================*/

int n,m,cnt,t;
struct node{
  int next;
  int to;
  double dis;
}e[N << 1];
struct nod{
  int pos;
  int u;
  int v;
  double val;
}bian[N << 1];
int head[N];
double w[N];
int vis[N];
int in[N];//入队次数
int id[N]; 

/*================================================*/

inline int read()
{
	int s = 0, f = 0;char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void add(int from,int to,double dis)
{
  e[++ cnt].to = to;
  e[cnt].dis = dis;
  e[cnt].next = head[from];
  head[from] = cnt;
  return;
}

bool check(double T)
{
  queue <int> qp;
  while(qp.size()) qp.pop();
  for(int i = 1;i <= n;i ++) w[i] = 1;
    // 有时候当你一直输出 0 时 ，看看这个 。。。 
  memset(head,0,sizeof(head));
  memset(vis,0,sizeof(vis));
  memset(in,0,sizeof(in));
  cnt = 0;
  // 数据清空
  for(int i = 1;i <= m;i ++) {//连边 
    if(id[bian[i].u] && id[bian[i].v] && ((bian[i].pos == 1 && id[bian[i].u] < id[bian[i].v] * (bian[i].val - T)) 
    || (bian[i].pos == 2 && id[bian[i].u] < id[bian[i].v] / (bian[i].val + T )))) return true; //剪枝 
    if(bian[i].pos == 1) add(bian[i].v ,bian[i].u ,bian[i].val - T);
    // x < y * (k - T) ;
    else add(bian[i].v ,bian[i].u ,1.0 / (bian[i].val + T));
    // x < y * 1 / (k + T);
  }
  for(int i = 1;i <= t;i ++) {
  // 由已知数据来建立超级源点， 所有的情况建立在这之上 
    if(id[i]) {
      add(0,i,id[i]);
      add(i,0,1.0 / id[i]); 
    }
  }
  w[0] = 1;
  vis[0] = 1;
  in[0] = 1;//入队次数 
  qp.push(0);
  while(!qp.empty()) {
    int x = qp.front();
    qp.pop();
    vis[x] = false;
    for(int i = head[x];i; i = e[i].next) {
      int y = e[i].to;
      if(w[y] < w[x] * e[i].dis) {
        w[y] = w[x] * e[i].dis;
        if(!vis[y]) {
          vis[y] = true;
          qp.push(y);
          ++ in[y];
          if(in[y] >= n + 1) return true;
        }
      }
    }
  }
  return false;
}
/*=================================================*/

signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
  n = read(); m = read(); t = read();
  double l = 0.0, r = 100.0; 
  for(int i = 1;i <= m;i ++) {
    bian[i].pos = read();
    bian[i].u = read();
    bian[i].v = read();
    bian[i].val = read() * 1.0;// 储存边的情况 
    // 因为之后的连边并不是 k 而是 （k - T） 
  }
  for(int i = 1;i <= t;i ++) {
    int iid,pts;
    iid = read(); pts = read();
    id[iid] = pts;//已有的成绩。 
  }
  double ans = -1;
  int iii = 0;
  while(r - l > EPS) {
    double mid = (r + l) / 2.0;
    if(check(mid)) {
      l = mid + EPS;
      ans = mid;
    }
    else r = mid - EPS;
    //cout << r <<" " << l <<" "<<iii ++ << endl;
  }
  if(ans == -1) printf("-1");
  else printf("%.10lf",ans);
  return 0;
}

这玩意跑的并不快，如果你想冲入 \(50 ms\) 以内，开始我们的优化 ：

1. 基本优化

  • \(SPFA\) 优化 ——— \(SLF\) 。 \(LLL\) 优化我没试。

  • 剪枝 ： 已知两个人成绩，且知道两者之间的女装关系符合条件一或条件二，可以直接返回，因为这时存在环路。

2 . 玄学优化

一般来说不靠谱... 考试千万别用。

  • 减少一下二分区间；

  • 减少一下精度；

  • 判断环的时候，如果入队次数大于 \(n + 1\) 改为 \(\sqrt{n + 1}\)，或者 \(\sqrt{\sqrt{n + 1}}\); 这个思想还是我从 P3084 最后一个点学来的。这玩意看 \(RP\) ，开方次数过多会导致判断出错，一般来说进了很多次队列就很有可能是环。

于是完美的从 \(270ms\) 卡到了 \(27ms\) 到了最优解 。

【Code】

/*
By : Ti_Despairy
Time : 2021,1,21;
思路 ：
知识点 ：
*/
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<queue>
#include<algorithm>
#include<stdlib.h>
#include<time.h>
#include<map>
#include<vector>
#include<set>
#define ull unsigned long long
#define ll long long
#define M 1000010
#define N 1010
#define qaq cout<<"可行QAQ"<<endl
#define INF 0x3f3f3f3f
using namespace std;
const int mod1 = 19260817;
const int mod2 = 19660813;
const double EPS = 1e-5;//确保精度 
/*================================================*/

int n,m,cnt,t;
struct node{
  int next;
  int to;
  double dis;
}e[N << 1];
struct nod{
  int pos;
  int u;
  int v;
  double val;
}bian[N << 1];
int head[N];
double w[N];
int vis[N];
int in[N];//入队次数
int id[N]; 

/*================================================*/

inline int read()
{
	int s = 0, f = 0;char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}

void add(int from,int to,double dis)
{
  e[++ cnt].to = to;
  e[cnt].dis = dis;
  e[cnt].next = head[from];
  head[from] = cnt;
  return;
}

bool check(double T)
{
  deque <int> qp;
  while(qp.size()) qp.pop_front();
  for(int i = 1;i <= n;i ++) w[i] = 1;
    // 有时候当你一直输出 0 时 ，看看这个 。。。 
  memset(head,0,sizeof(head));
  memset(vis,0,sizeof(vis));
  memset(in,0,sizeof(in));
  cnt = 0;
  // 数据清空
  for(int i = 1;i <= m;i ++) {//连边 
    if(id[bian[i].u] && id[bian[i].v] && ((bian[i].pos == 1 && id[bian[i].u] < id[bian[i].v] * (bian[i].val - T)) 
    || (bian[i].pos == 2 && id[bian[i].u] < id[bian[i].v] / (bian[i].val + T )))) return true;
    if(bian[i].pos == 1) add(bian[i].v ,bian[i].u ,bian[i].val - T);
    // x < y * (k - T) ;
    else add(bian[i].v ,bian[i].u ,1.0 / (bian[i].val + T));
    // x < y * 1 / (k + T);
  }
  for(int i = 1;i <= t;i ++) {
  // 由已知数据来建立超级源点， 所有的情况建立在这之上 
    if(id[i]) {
      add(0,i,id[i]);
      add(i,0,1.0 / id[i]); 
    }
  }
  w[0] = 1;
  vis[0] = 1;
  in[0] = 1;//入队次数 
  qp.push_back(0);
  while(!qp.empty()) {
    int x = qp.front();
    qp.pop_front();
    //puts("LKP AK IOI");
    vis[x] = false;
    for(int i = head[x];i; i = e[i].next) {
      int y = e[i].to;
      if(w[y] < w[x] * e[i].dis) {
        w[y] = w[x] * e[i].dis;
        if(!vis[y]) {
          vis[y] = true;
          if(!qp.empty() && w[y] < w[qp.front()]) qp.push_back(y);
          else qp.push_front(y);
          ++ in[y];
          if(in[y] >= sqrt(sqrt(n + 1))) return true;
        }
      }
    }
  }
  return false;
}
/*=================================================*/

signed main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
  n = read(); m = read(); t = read();
  double l = 0.0, r = 4.0; 
  for(int i = 1;i <= m;i ++) {
    bian[i].pos = read();
    bian[i].u = read();
    bian[i].v = read();
    bian[i].val = read() * 1.0;// 储存边的情况 
    // 因为之后的连边并不是 k 而是 （k - T） 
  }
  for(int i = 1;i <= t;i ++) {
    int iid,pts;
    iid = read(); pts = read();
    id[iid] = pts;//已有的成绩。 
  }
  double ans = -1;
  int iii = 0;
  while(r - l > EPS) {
    double mid = (r + l) / 2.0;
    if(check(mid)) {
      l = mid + EPS;
      ans = mid;
    }
    else r = mid - EPS;
    //cout << r <<" " << l <<" "<<iii ++ << endl;
  }
  if(ans == -1) printf("-1");
  else printf("%.10lf",ans);
  return 0;
}
上一篇：1007 素数对猜想


下一篇：1007-3_4计算无限序列