图论之路径条数专题

一直忙着金工实习+蓝桥杯,好久没有看图论了,今天就小试几题享受下被虐的快感。

1.最短路+拓扑

首先来几个结论:

1.最短路图没有环(可以用反证法证明)

2.dis[u]+edge[u,v]=dis[v],那么u,v端点的边一定在最短路图上。

因此,我们就可以先枚举起始点跑SPFA,然后把最短路找出来,假如一个边的端点为u,v,那么经过它的为cnt1[u]*cnt2[v],cnt1为正着最短路图上过u的边,cnt2为反着(注意到v结束也是一种,所以结尾后+1)。

因此,我们求两边拓扑排序即可,下面是AC代码(这里正反图用奇偶存储来区别):

#include<bits/stdc++.h>
#define mod 1000000007
using namespace std;const int N=1502;
const int M=100010;
bool vis[N];
int dis[N],in1[N],in2[N],cnt1[N],cnt2[N];
int n,m,u,v,w,head[N],is[M],cnt=1;
int ans[M];
struct node{int dian,next,zhi;
}edge[M];
void add(int u,int v,int w){//i&1为反图 edge[++cnt].dian=v;edge[cnt].zhi=w;edge[cnt].next=head[u];head[u]=cnt;edge[++cnt].dian=u;edge[cnt].zhi=w;edge[cnt].next=head[v];head[v]=cnt; 
}
void spfa(int s){memset(vis,0,sizeof(vis));memset(dis,0x7f7f7f7f,sizeof(dis));queue<int> q;vis[s]=1;q.push(s);dis[s]=0;while(!q.empty()){int ck=q.front();q.pop();vis[ck]=0;for(int i=head[ck];i!=-1;i=edge[i].next){if(i&1) continue;if(dis[edge[i].dian]>dis[ck]+edge[i].zhi){dis[edge[i].dian]=dis[ck]+edge[i].zhi;if(!vis[edge[i].dian]){vis[edge[i].dian]=1;q.push(edge[i].dian);}}}}
}
void new1(){memset(is,0,sizeof(is));memset(in1,0,sizeof(in1));memset(in2,0,sizeof(in2));for(int u=1;u<=n;u++){for(int i=head[u];i!=-1;i=edge[i].next){if(i&1) continue;if(dis[u]+edge[i].zhi==dis[edge[i].dian]){is[i]=1;is[i^1]=1;in1[edge[i].dian]++;in2[u]++;}}}
}
void topo(int s){memset(cnt1,0,sizeof(cnt1));memset(cnt2,0,sizeof(cnt2));queue<int> q;q.push(s);cnt1[s]=1;while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){if(!is[i]||(i&1)) continue;int v=edge[i].dian;in1[v]--;cnt1[v]=(cnt1[v]+cnt1[u])%mod;if(!in1[v]) q.push(v);}}for(int i=1;i<=n;i++){if(!in2[i]){cnt2[i]=1;q.push(i);}}while(!q.empty()){int u=q.front();q.pop();for(int i=head[u];i!=-1;i=edge[i].next){if(!is[i]||!(i&1)) continue;int v=edge[i].dian;in2[v]--;cnt2[v]=(cnt2[v]+cnt2[u])%mod;if(!in2[v]){q.push(v);cnt2[v]++;//自己 }}}
}
void cal(){for(int u=1;u<=n;u++){for(int i=head[u];i!=-1;i=edge[i].next){if((i&1)||!is[i]) continue;int v=edge[i].dian;ans[i>>1]=(ans[i>>1]+cnt1[u]*cnt2[v]%mod)%mod;}}
}
void solve(){for(int i=1;i<=n;i++){spfa(i);new1();topo(i);cal();}for(int i=1;i<=m;i++) printf("%d\n",ans[i]);
}
int main(){cin>>n>>m;memset(head,-1,sizeof(head));for(int i=1;i<=m;i++){scanf("%d%d%d",&u,&v,&w);add(u,v,w);}solve();return 0;
}

2.最短路+DP

首先跑个最短路,然后我们令f[i][j]表示走到i不超过d+j的条数。

易得状态转移方程:f[x][k]=\sum(f[y][dis[x]+k-dis[y]-len2[x][y])%p;

至于顺序我们直接记忆化搜素即可。

这里有个比较麻烦的细节:

如何判断0环?

1.不是一有0环就-1,当你的0环不在最短路+k涉及的路径上它起不了作用,那么这如何判?

注意到此时dis[x]+k-dis[y]-len2[x][y]为负值,我们判一下这种情况即可。

2.当一个二维位置即同一个点,同一个小于距离出现时,说明0环,判-1.

因此我们还要用v[n][55]来记录有没有访问过(注意dfs完后归0操作)

3.注意到0环涉及起点1的情况,这也是为什么起点设在n+1源点而不是1的原因。

下面是AC代码:

#include<bits/stdc++.h>
using namespace std;
const int N=100000;
int t,n,m,k,p,a,b,c,flag;
vector<int> edge[N+1],len[N+1];
vector<int> edge1[N+1],len2[N+1];
int dis[N+1],vis[N+1];
int f[N+1][55];
bool v[N+1][55];
struct ty{int x,dis;bool operator< (const ty &a) const{return dis>a.dis;}
};
priority_queue<ty> q;
void dij(int s){memset(dis,0x7f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;q.push({s,0});while(!q.empty()){ty tmp=q.top();q.pop();if(vis[tmp.x]) continue;vis[tmp.x]=1;for(int i=0;i<edge[tmp.x].size();i++){int y=edge[tmp.x][i];if(dis[y]>dis[tmp.x]+len[tmp.x][i]){dis[y]=dis[tmp.x]+len[tmp.x][i];q.push({y,dis[y]});}}}
}
int dfs(int x,int k){if(f[x][k]!=-1) return f[x][k];f[x][k]=0;v[x][k]=1;for(int i=0;i<edge1[x].size();i++){int y=edge1[x][i];int t=dis[x]+k-dis[y]-len2[x][i];if(t<0) continue;if(v[y][t]) flag=1;if(flag) return 0;    f[x][k]=(f[x][k]+dfs(y,t))%p;}v[x][k]=0;return f[x][k];
}
int main(){cin>>t;while(t--){scanf("%d%d%d%d",&n,&m,&k,&p);for(int i=1;i<=n+1;i++){edge[i].clear();len[i].clear();edge1[i].clear();len2[i].clear();}for(int i=1;i<=m;i++){scanf("%d%d%d",&a,&b,&c);edge[a].push_back(b);len[a].push_back(c);edge1[b].push_back(a);len2[b].push_back(c);}edge[n+1].push_back(1);len[n+1].push_back(0);edge1[1].push_back(n+1);len2[1].push_back(0);dij(n+1);memset(f,-1,sizeof(f));memset(v,0,sizeof(v));f[n+1][0]=1;int ans=0;flag=0;for(int i=0;i<=k;i++){ans=(ans+dfs(n,i))%p;}if(flag) printf("-1\n");else printf("%d\n",ans);}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/290133.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Redis】redis主从复制

概述 常见的Redis高可用的方案包括持久化、主从复制&#xff08;及读写分离&#xff09;、哨兵和集群。其中持久化侧重解决的是Redis数据的单机备份问题&#xff08;从内存到硬盘的备份&#xff09;&#xff1b;而主从复制则侧重解决数据的多机热备。此外&#xff0c;主从复制…

AI浸入社交领域,泛娱乐APP如何抓住新风口?

2023年是大模型技术蓬勃发展的一年&#xff0c;自ChatGPT以惊艳姿态亮相以来&#xff0c;同年年底多模态大模型技术在国内及全球范围内的全面爆发&#xff0c;即模型能够理解并生成包括文本、图像、视频、音频等多种类型的内容。例如&#xff0c;基于大模型的文本到图像生成工具…

FPGA 图像边缘检测(Canny算子)

1 顶层代码 timescale 1ns / 1ps //边缘检测二阶微分算子&#xff1a;canny算子module image_canny_edge_detect (input clk,input reset, //复位高电平有效input [10:0] img_width,input [ 9:0] img_height,input [ 7:0] low_threshold,input [ 7:0] high_threshold,input va…

2024.3.28学习笔记

今日学习韩顺平java0200_韩顺平Java_对象机制练习_哔哩哔哩_bilibili 今日学习p286-p294 继承 继承可以解决代码复用&#xff0c;让我们的编程更加靠近人类思维&#xff0c;当多个类存在相同的属性和方法时&#xff0c;可以从这些类中抽象出父类&#xff0c;在父类中定义这些…

从人工智能入门到理解ChatGPT的原理与架构的第一天(First)(含机器学习特征工程详解)

目录 一.ChatGPT的发展历程 二.Attention is all you need 三.对于GPT-4的智能水平评估 四.大语言模型的技术演化 1.从符号主义到连接主义 2.特征工程 2.1数据探索 2.2数据清洗 2.3数据预处理 2.3.1无量纲化 2.3.1.1标准化 2.3.1.2区间缩放法 2.3.1.3标准化与归一…

42 ajax 下载文件未配置 responseType blob 导致的文件异常

前言 这是一个最近的关于文件下载碰到的一个问题 主要的情况是, 基于 xhr 发送请求, 获取下载的文件 然后 之后 xhr 这边拿到 字节序列之后, 封装 blob 来进行下载 然后 最开始我们这边没有配置 responseType 为 blob, arraybuffer, 然后 导致下载出来的 文件大小超过了…

语音模块摄像头模块阿里云结合,实现垃圾的智能识别

语音模块&摄像头模块&阿里云结合 文章目录 语音模块&摄像头模块&阿里云结合1、实现的功能2、配置2.1 软件环境2.2 硬件配置 3、程序介绍3.1 程序概况3.2 语言模块SDK配置介绍3.3 程序文件3.3.1 开启摄像头的程序3.3.2 云端识别函数( Py > C ) & 串口程序…

Flask学习(六):蓝图(Blueprint)

蓝图&#xff08;Blueprint&#xff09;&#xff1a;将各个业务进行区分&#xff0c;然后每一个业务单元可以独立维护&#xff0c;Blueprint可以单独具有自己的模板、静态文件或者其它的通用操作方法&#xff0c;它并不是必须要实现应用的视图和函数的。 Demo目录结构&#xf…

基于js css的瀑布流demo

要实现照片按照瀑布流展示&#xff0c;写个小demo&#xff0c;记录下。 瀑布流实现思路如下&#xff1a; CSS 弹性布局对 3 列按横向排列&#xff0c;对每一列内部按纵向排列 html代码&#xff1a; <div class"content"></div> css代码&#xff1a; …

2.4 比较检验 机器学习

目录 常见比较检验方法 总述 2.4.1 假设检验 2.4.2 交叉验证T检验 2.4.3 McNemar 检验 接我们的上一篇《性能度量》&#xff0c;那么我们在某种度量下取得评估结果后&#xff0c;是否可以直接比较以评判优劣呢&#xff1f;实际上是不可以的。因为我们第一&#xff0c;测试…

Unity 实现鼠标左键进行射击

发射脚本实现思路 分析 确定用户交互方式&#xff1a;通过鼠标左键点击发射子弹。确定子弹发射逻辑&#xff1a;每次点击后有一定时间间隔才能再次发射。确定子弹发射源和方向&#xff1a;子弹从枪口&#xff08;Transform&#xff09;位置发射&#xff0c;沿枪口方向前进。 变…

iOS客户端自动化UI自动化airtest+appium从0到1搭建macos+脚本设计demo演示+全网最全最详细保姆级有步骤有图

Android客户端自动化UI自动化airtest从0到1搭建macos脚本设计demo演示全网最全最详细保姆级有步骤有图-CSDN博客 避坑系列-必读&#xff1a; 不要安装iOS-Tagent &#xff0c;安装appium -这2个性质其实是差不多的都是为了安装wda。注意安装appium最新版本&#xff0c;安装完…

Gitlab CI---could not read username for xxx: no such device or address

0 Preface/Foreword 项目开发中&#xff0c;经常会使用第三方的算法或者功能&#xff0c;那么就需要把对应的repo以子模块的方式添加到当前repo中。 添加命令&#xff1a; git submodule add <URL> 1 问题表现 子模块添加成功&#xff0c;但是GitLab CI阶段&#xff…

基于Python的电商特产数据可视化分析与推荐系统

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长 QQ 名片 :) 1. 项目简介 利用网络爬虫技术从某东采集某城市的特产价格、销量、评论等数据&#xff0c;经过数据清洗后存入数据库&#xff0c;并实现特产销售、市场占有率、价格区间等多维度的可视化统计分析&#xff0c;并…

filebox在线文件管理工具V1.11.1.1查分吧修改自用版免费分享[PHP]

* 基于:https://down.chinaz.com/soft/35899.htm * 查分吧 修改自用版今日对外分享(自2016年1.10版本以来一直用他云开发:Web环境即时看效果) * 也可以用于本人很多txt/csv通用查询系统的在线管理后台管理数据 * 默认登陆账号filebox密码nidemima * 修改账号密码:21-22行;获取…

Python人工智能:气象数据可视化的新工具

Python是功能强大、免费、开源&#xff0c;实现面向对象的编程语言&#xff0c;在数据处理、科学计算、数学建模、数据挖掘和数据可视化方面具备优异的性能&#xff0c;这些优势使得Python在气象、海洋、地理、气候、水文和生态等地学领域的科研和工程项目中得到广泛应用。可以…

MySQL进阶-----索引的语法与SQL性能分析

目录 前言 一、索引语法 1.SQL语法 2.案例演示 二、SQL性能分析 三、慢查询日志 1.开启日志 2.测试样例 四、profile详情 1.开启profile 2.profile测试SQL语句 五、explain详情 1.语法结构 2.执行顺序示例&#xff08;id&#xff09; 3.执行性能示例(type) 前言 本…

fastadmin学习04-一键crud

FastAdmin 默认内置一个 test 表&#xff0c;可根据表字段名、字段类型和字段注释通过一键 CRUD 自动生成。 create table fa_test (id int unsigned auto_increment comment ID primary key,user_id int(10) default 0 null…

蓝桥杯物联网遇见的重大BUG及其产生原因和解决方法

BUG列表 1、ADC的RP2显示一直为0&#xff1a;2、LORX_Tx发送数据乱码&#xff1a;3、strcmp比较char a[2] {1, 2}与“12”字符串是否相等板子会死机&#xff1a;4、LORA_Tx和LORA_Rx放一起会接收不到数据&#xff1a;5、RTC获取到静止时间&#xff1a;6、ADC获取RP1和RP2模拟量…

Vue 03 组件通信

Vue学习 Vue 0301 浏览器本地存储localStorageSessionStorage案例 todolist的完善 02 组件自定义事件Custom Events基本使用解绑自定义事件注意事项①② 总结案例 todolist的完善 03 全局事件总线GlobalEventBus案例 todolist的完善 04 消息的订阅与发布案例 todolist的完善 05…