自动搬运

查看原文

来自洛谷，原作者为

	EricQian 问征夫以前路，恨晨光之熹微。

搬运于2025-08-24 22:05:20，当前版本为作者最后更新于2020-10-07 17:15:25，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

$\leftarrow$ 我的差分约束专题

原题链接：P4926 [1007]倍杀测量者

题意

给出一系列不等式：

$$x_{a_i}\ge (k_i-t)\times x_{b_i}~~~\&~~~(k_i+t)\times x_{a_i}>x_{b_i} $$

以及一些 $x_i$ 的值 。

求出最大的 $t$ 使得不等式无解 。

---

题解

算法：差分约束 $+$ 二分答案 。

1. 连边

首先对不等式进行拆分化简：

$$x_{a_i}\ge (k_i-t)\times x_{b_i}$$ $$\log_2{(x_{a_i})}\ge \log_2{(x_{b_i})}+\log_2{(k_i-t)} $$

连边 add(b,a,log2(k-t))

$$(k_i+t)\times x_{a_i}>x_{b_i}$$ $$\log_2{(x_{a_i})}+\log_2{(k_i+t)}>\log_2{(x_{b_i})} $$$$\log_2{(x_{a_i})}>\log_2{(x_{b_i})}-\log_2{(k_i+t)} $$

由于本题有精度 $10^{-5}$ 的容量范围，所以我们可以连边 add(b,a,-log2(k+t))

（具体实现连边操作时只用记录 $k$ 的值，$t$ 根据边的种类在差分的时候分类讨论。）

2. 判断无解

输出 -1 仅当 $t=0$ 时不等式仍旧有解 。

3. 二分答案

二分一个 $t$ ，判断这个时候不等式是否有解 。输出答案 。

上AC代码（去掉了不必要的部分）：

#define inf 0x7f7f7f7f
#define Maxn 5005
int n,s,t,tot;
int cnt[Maxn],hea[Maxn],nex[Maxn*2],ver[Maxn*2],typ[Maxn*2];
double ds[Maxn],edg[Maxn*2];
bool inq[Maxn];

inline void add(int x,int y,double d,int Type)
{
	 ver[++tot]=y,edg[tot]=d,typ[tot]=Type,nex[tot]=hea[x],hea[x]=tot;
}

bool spfa(double tmp) // tmp 这里表示上面说的 t 的值
{
	 for(int i=0;i<=n;i++) ds[i]=-inf,cnt[i]=0,inq[i]=false; ds[n+1]=0;
	 queue<int> q; q.push(n+1),inq[n+1]=true;
	 while(!q.empty())
	 {
	 	 int cur=q.front(); q.pop(),inq[cur]=false;
	 	 for(int i=hea[cur];i;i=nex[i])
	 	 {
	 	 	 double w=edg[i]; // 类型为 3 的边 
	 	 	 if(typ[i]==1) w=log2(edg[i]-tmp); // 类型为 1 的边 
	 	 	 if(typ[i]==2) w=-log2(edg[i]+tmp); // 类型为 2 的边 
	 	 	 if(ds[ver[i]]<ds[cur]+w)
	 	 	 {
	 	 	 	 ds[ver[i]]=ds[cur]+w,cnt[ver[i]]=cnt[cur]+1;
	 	 	 	 if(cnt[ver[i]]>=n+2) return true; // 判断无解 
	 	 	 	 else if(!inq[ver[i]]) inq[ver[i]]=true,q.push(ver[i]);
			 }
		 }
	 }
	 return false; // 此时有解 
}

double x,l=0,r=10,ans,mid;
scanf("%d%d%d",&n,&s,&t);
for(int i=0;i<=n;i++) add(n+1,i,0,3);
for(int i=1,opt,a,b;i<=s;i++)
{
	 scanf("%d%d%d%lf",&opt,&a,&b,&x),add(b,a,x,opt);
	 if(opt==1) r=fmin(r,x);
}
for(int i=1,c;i<=t;i++) scanf("%d%lf",&c,&x),add(0,c,log2(x),3),add(c,0,-log2(x),3);
if(!spfa(0)) printf("-1\n");
else
{
	 while(r-l>cha) // cha 是 0.00001 保证精度 
	 {
	 	 mid=(l+r)/2.0;
	 	 if(spfa(mid)) ans=mid,l=mid+cha;
	 	 else r=mid-cha;
	 }
	 printf("%.6lf\n",ans);
}

以上代码目前在最优解第一面 ^_^