差分约束中,只能表示大于,小于,等于三种关系,不包含倍数这种关系。
所以需要对倍数进行合理的转换,也就是进行log化处理,这样就可以把倍
数变成数值的差值
//对于相等以及不需要转化的关系,我们可以设立一个变量为边的种类
//这样会减少许多运算量
#include <bits/stdc++.h>
using namespace std;
const int M=5005;
const double eps=1e-4;
int h[M],ne[M],e[M],type[M],tot;
double w[M];
void add(int from,int to,double wi,int typ) {
e[++tot]=to;
ne[tot]=h[from];
w[tot]=wi;
type[tot]=typ;
h[from]=tot;
}
int n,m,t;
int cnt[M];
double dis[M];
bool vis[M];
bool spfa(double x) {
for(int i=0;i<=n+1;i++)
dis[i]=-1e9,cnt[i]=vis[i]=0;
queue<int>q;
dis[0]=0;
q.push(0);
vis[0]=1;
while(!q.empty()) {
int now=q.front();
q.pop();
vis[now]=0;
for(int i=h[now];i;i=ne[i]) {
int to=e[i];
double wi=w[i];
if(type[i]==1)wi=log2(wi-x);
else if(type[i]==2)wi=-log2(wi+x);
if(dis[to]<dis[now]+wi) {//跑的是最大路
dis[to]=dis[now]+wi;
cnt[to]=cnt[now]+1;
if(cnt[to]>n+1)return 1;//判断有没有环
if(vis[to]==0)q.push(to),vis[to]=1;
}
}
}
return 0;
}
//最短路的差分约束,会有最大值进行约束
//最长路的差分约束,会有最小值进行约束
int main() {
double l=0,r=10;
cin>>n>>m>>t;
for(int i=1;i<=m;i++) {
int op,x,y;
double wi;
cin>>op>>x>>y>>wi;
add(y,x,wi,op);
if(op&1)r=fmin(r,wi);
}
for(int i=1;i<=n;i++)add(0,i,0,3);//保证所有的边都是大于0的
for(int i=1;i<=t;i++) {
int c;double x;
cin>>c>>x;
add(0,c,log2(x),3);
add(c,0,-log2(x),3);
}
//特殊边
if(spfa(0)==0)return cout<<-1,0;
//很显然k==0的时候条件是最容易达成的,首先特判一下子就可以了
int cnt=0;
while(r-l>eps) {//二分,找到最大值
double mid=(l+r)/2;
if(spfa(mid))l=mid;
else r=mid;
}
printf("%.6lf\n",l);
return 0;
}
原文地址:http://www.cnblogs.com/basicecho/p/16881488.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性