(JZ4246)2019.01.29【NOIP提高组】模拟B组 2.san(道路不和谐,把你哔哩哔哩掉)

2024-01-30 05:48

本文主要是介绍(JZ4246)2019.01.29【NOIP提高组】模拟B组 2.san(道路不和谐,把你哔哩哔哩掉),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【五校联考6day2】san

Description

小明经常去N 个地点,其中有些地点之间有直接的无向道路(共M 条这样的道路),可以直接互相到达,这些道路的长短不一。由于小明对这些道路都很熟悉,无论起点和终点在哪里,总能走最短路。小明有严重的强迫症,认为奇数很不和谐,如果他某一天从一个地点去另一个地点走过的路程是奇数,就会很不爽,但他又不想白白多走路,所以遇到最短路长度是奇数的情况就只能忍了。
如果从某个地点A 到另一个地点B 的最短路径长度为奇数,则称这条最短路径为“不和谐最短路”。如果一条不和谐最短路上包含地点C,则称它为“经过C 的不和谐最短路”。现在请你编程求出对于每个地点,经过它的不同的不和谐最短路数量。两条最短路不同,当且仅当它们途径的地点的序列不同。

Input

第一行两个正整数N;M,含义见题面。
接下来M 行,每行三个正整数Ai;Bi;Li,表示一条无向道路的两端和长度。

Output

N 行每行一个整数,第i 行表示经过第i 个点的不同的不和谐最短路条数。

Sample Input
4 4
1 4 1
1 2 1
3 4 100
2 3 2

Sample Output
6
4
2
2
样例说明
长度为奇数的最短路有:1 → 2; 1 → 2 → 3; 1 → 4; 2 → 1; 3 → 2 → 1; 4 → 1。
这些路径中四个点的经过次数分别为6, 4, 2, 2。
其它一些路,如1 → 4 → 3 不是最短路,2 → 3 是最短路但长度为2,是偶数。这些路都不计入答案。

Data Constraint

对于50% 的数据,N ≤ 100;
对于全部数据,N ≤ 1000;M ≤ 3000,每条路的长度不超过1000。
保证图连通,无自环重边。

纪中题解:

3.1 50 分算法
N = 100,可以枚举起点和终点,用各种算法枚举两点间所有最短路并累加答案,复杂度一般为 O(N3)。
3.2 满分算法
题目中的图是一般图,结构复杂没有规律。考虑枚举起点并计算单源最短路,保留所有最短路中的边(有向),原图就变成了一个 DAG,可以很方便地在上面进行拓扑排序,DP 等。再考虑长度为奇数的最短路,从一个点断开,一定是一边长度为奇数,另一边长度为偶数。因此可以在 DAG 上 DP 计算从起点到达每个点的奇偶最短路径分别有几条,再逆序 DP 计算从每个点出发的奇偶最1短路径条数,在后面的 DP 过程中顺便统计答案。这样对每个起点算一遍。复杂度 O(NM log N)。

st↗ory↘ time→(请脑补卡面来打woz我儿子的音效):

以下是Kamen Rider 数组开小的变声音效┓( ´∀` )┏
    TLE!WA!Best Match!

   动次打次动次打次

   Are you ready?钢之Moonsault!(粤语空耳:佢吊你老母!)TLEWA!Yeah!

ε=(´ο`*)))唉

个人补充:

   用SPFA跑最短路,考虑枚举起点并计算单源最短路,将无向图便乘有向图。
   可以用dp,也可以用dfs来做

#include<cstdio>
#include<queue>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1010;
struct node{int to,next,w;
}a[N*6];
int n,m,j;
int tot,ls[N],f[N][N],ans[N];
bool v[N];
queue<int> q;
void add(int x,int y,int w){a[++tot].to=y;a[tot].next=ls[x];a[tot].w=w;ls[x]=tot;
}void spfa(int s){memset(f[s],0x3f,sizeof(f[s]));q.push(s);v[s]=1;f[s][s]=0;while(!q.empty()){int x=q.front();q.pop();for(int i=ls[x]; i; i=a[i].next){int y=a[i].to;if(f[s][x]+a[i].w<f[s][y]){f[s][y]=f[s][x]+a[i].w;if(!v[y]){v[y]=1;q.push(y);}}}v[x]=false;}
}int dfs(int x){int w=(f[j][x]&1);ans[x]+=w;for(int i=ls[x]; i; i=a[i].next){int y=a[i].to,z;if(f[j][x]+a[i].w==f[j][y]){w+=(z=dfs(y));ans[x]+=z;}}return w;
}int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int x,y,z;scanf("%d%d%d",&x,&y,&z);add(x,y,z); add(y,x,z);}for(int i=1; i<=n; i++) spfa(i);for(j=1; j<=n; j++) dfs(j);for(int i=1; i<=n; i++) printf("%d\n",ans[i]);
}

这篇关于(JZ4246)2019.01.29【NOIP提高组】模拟B组 2.san(道路不和谐,把你哔哩哔哩掉)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/659267

相关文章

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

键盘快捷键:提高工作效率与电脑操作的利器

键盘快捷键:提高工作效率与电脑操作的利器 在数字化时代,键盘快捷键成为了提高工作效率和优化电脑操作的重要工具。无论是日常办公、图像编辑、编程开发,还是游戏娱乐,掌握键盘快捷键都能带来极大的便利。本文将详细介绍键盘快捷键的概念、重要性、以及在不同应用场景中的具体应用。 什么是键盘快捷键? 键盘快捷键,也称为热键或快捷键,是指通过按下键盘上的一组键来完成特定命令或操作的方式。这些快捷键通常涉及同

CSP 2023 提高级第一轮 CSP-S 2023初试题 完善程序第二题解析 未完

一、题目阅读 (最大值之和)给定整数序列 a0,⋯,an−1,求该序列所有非空连续子序列的最大值之和。上述参数满足 1≤n≤105 和 1≤ai≤108。 一个序列的非空连续子序列可以用两个下标 ll 和 rr(其中0≤l≤r<n0≤l≤r<n)表示,对应的序列为 al,al+1,⋯,ar​。两个非空连续子序列不同,当且仅当下标不同。 例如,当原序列为 [1,2,1,2] 时,要计算子序列 [

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

如何提高 GitHub 的下载速度

如何提高 GitHub 的下载速度 文章目录 如何提高 GitHub 的下载速度1. 注册账号2. 准备好链接3. 创建仓库4. 在码云上下载代码5. 仓库更新了怎么办 一般来说,国内的朋友从 GitHub 上面下载代码,速度最大是 20KB/s,这种龟速,谁能忍受呢? 本文介绍一种方法——利用“码云”,可以大大提高下载速度,亲测有效。 1. 注册账号 去“码云”注册一

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

【算法专场】模拟(下)

目录 前言 38. 外观数列 算法分析 算法思路 算法代码 1419. 数青蛙 算法分析 算法思路 算法代码  2671. 频率跟踪器 算法分析 算法思路 算法代码 前言 在前面我们已经讲解了什么是模拟算法,这篇主要是讲解在leetcode上遇到的一些模拟题目~ 38. 外观数列 算法分析 这道题其实就是要将连续且相同的字符替换成字符重复的次数+

模拟实现vector中的常见接口

insert void insert(iterator pos, const T& x){if (_finish == _endofstorage){int n = pos - _start;size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;reserve(newcapacity);pos = _start + n;//防止迭代