当前位置: 首页 > news >正文

差分约束乘法改加减

洛谷P4926 [1007] 倍杀测量者

image

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
const double INF=1e18;
const double eps=1e-7;
struct node{int v;double k;int tp;
};
vector<node> edges[N];
int n,s,t,cnt[N];
bool vis[N];
double dp[N];
bool spfa(double T){for(int i=0;i<=n+1;i++){dp[i]=-INF;vis[i]=false;cnt[i]=0;}queue<int> q;q.push(n+1);dp[n+1]=0;vis[n+1]=true;while(q.size()){int u=q.front();q.pop();vis[u]=false;for(auto &[v,k,tp]:edges[u]){double w=k;if(tp==1){w=log2(w-T);}else if(tp==2){w=-log2(w+T);}if(dp[v]<dp[u]+w){dp[v]=dp[u]+w;cnt[v]=cnt[u]+1;if(!vis[v]){vis[v]=true;q.push(v);}if(cnt[v]>=n+2)return true;}}}return false;
}int main(){// cin.tie(nullptr)->sync_with_stdio(false);cin>>n>>s>>t;double l=0,r=10;for(int i=0;i<=n;i++){edges[n+1].push_back({i,0,3});}for(int i=1;i<=s;i++){int op,a,b,k;cin>>op>>a>>b>>k;edges[b].push_back({a,(double)k,op});if(op==1)r=fmin(r,k-eps);}for(int i=1;i<=t;i++){int c,x;cin>>c>>x;edges[c].push_back({0,-log2(x),3});edges[0].push_back({c,log2(x),3});}if(!spfa(0)){cout<<-1<<endl;return 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.hskmm.com/?act=detail&tid=26811

相关文章:

  • 01-方法-课后作业
  • 应用程序io接口
  • 边缘数据库近期想法(2)
  • 方法-课后作业1
  • io软件的层次结构
  • 2025年- H57-Lc165--994.腐烂的橘子(图论,广搜)--Java版 - 教程
  • 3,信号与槽机制 - 教程
  • 课后思考及作业:方法
  • 2025国庆Day7
  • 月嫂面试题
  • 把握一个Makefile的脉络
  • 笔记 基础算法
  • P10068 [CCO 2023] Line Town
  • AI元人文:共识锚定与智慧剪枝——构建人机共生认知经济体的完善理论体系与实践路径
  • 出题系统
  • io控制方式
  • Java课后作业
  • 我 是 人 机
  • 28定律及其扩展衍生
  • 3516cv610在sample_aiisp上多创一路编码流,方法 - 详解
  • 2025氧化石墨烯、羧基化石墨烯、巯基化石墨烯、羟基化石墨烯、氨基化石墨烯、氮掺杂氧化石墨烯、氮掺杂石墨烯最新推荐、全面剖析优质厂商实力与选购要点
  • 2025-10-8模拟测验
  • QBXT2025S刷题 Day7
  • 【Python】调用C++
  • 方法作业
  • [100ask_imx6ullpro] buildroot构建emmc镜像并烧录
  • 2025 汽车改装公司最新推荐榜:一站式服务生态企业盘点,含奔驰宝马新能源改装及新锐品牌权威测评重庆宝马汽车改装/重庆新能源汽车改装/重庆汽车改装贴膜/重庆汽车改装轮毂刹车公司推荐
  • 2025 布袋包装厂家最新推荐榜:自贸区实力厂商领衔,含手提袋、帆布袋等全品类,年销 500 万级生产商精选无纺布袋/布袋生产/云南布袋包装/茶叶布袋厂家推荐
  • 2025 年成型机厂家最新推荐排行榜:冷弯 / 光伏支架 / 门业 / 建材等领域设备企业精度与耐用性实测点评魔方方管/门框角码/导槽/底樑/光伏支架/C型钢成型机厂家推荐
  • 2025 年平板机厂家最新推荐榜单:聚焦技术实力与市场口碑,5 大优质品牌实测点评