hiho 1515 : 分数调查 简单bfs
2024-08-28 00:10:06
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
小Hi的学校总共有N名学生,编号1-N。学校刚刚进行了一场全校的古诗文水平测验。
学校没有公布测验的成绩,所以小Hi只能得到一些小道消息,例如X号同学的分数比Y号同学的分数高S分。
小Hi想知道利用这些消息,能不能判断出某两位同学之间的分数高低?
输入
第一行包含三个整数N, M和Q。N表示学生总数,M表示小Hi知道消息的总数,Q表示小Hi想询问的数量。
以下M行每行三个整数,X, Y和S。表示X号同学的分数比Y号同学的分数高S分。
以下Q行每行两个整数,X和Y。表示小Hi想知道X号同学的分数比Y号同学的分数高几分。
对于50%的数据,1 <= N, M, Q <= 1000
对于100%的数据,1 <= N, M, Q<= 100000 1 <= X, Y <= N -1000 <= S <= 1000
数据保证没有矛盾。
输出
对于每个询问,如果不能判断出X比Y高几分输出-1。否则输出X比Y高的分数。
- 样例输入
-
10 5 3
1 2 10
2 3 10
4 5 -10
5 6 -10
2 5 10
1 10
1 5
3 5 - 样例输出
-
-1
20
0
开始以为是存在环(矛盾的分数),这样的话,可能要判环。读完题发现没有矛盾存在,这样的话并查集+bfs乱搞
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<memory>
using namespace std;
const int maxn=;
int Laxt[maxn],Next[maxn],To[maxn],V[maxn],cnt=;
int fa[maxn],scr[maxn];//fa是分组,score代表相对分数。
void _add(int u,int v,int s){
Next[++cnt]=Laxt[u];
Laxt[u]=cnt;
To[cnt]=v;
V[cnt]=s;
}
void _dfs(int u){
for(int i=Laxt[u];i;i=Next[i]){
if(!fa[To[i]]){
fa[To[i]]=fa[u];
scr[To[i]]=scr[u]-V[i];
_dfs(To[i]);
}
}
}
int main()
{
int n,m,q,i,x,y,s;
scanf("%d%d%d",&n,&m,&q);
for(i=;i<=m;i++){
scanf("%d%d%d",&x,&y,&s);
_add(x,y,s);
_add(y,x,-s);
}
for(i=;i<=n;i++)
if(!fa[i]){
fa[i]=i;
_dfs(i);
}
for(i=;i<=q;i++){
scanf("%d%d",&x,&y);
if(fa[x]!=fa[y]) printf("-1\n");
else printf("%d\n",scr[x]-scr[y]);
}
return ;
}
最新文章
- 不从SD卡启动树莓派2
- 让UserControl能显示焦点状态
- ODAC(V9.5.15) 学习笔记(十八)	数据集缓冲模式
- Effective Java 45 Minimize the scope of local variables
- python 读写文件和设置文件的字符编码
- ios uitableviewcell动态计算高度
- 晒下自己App广告平台积分墙收入,顺便点评几个广告平台
- VPN怎么连?
- 二、JSP的3个编译指令,7个动作指令,9个内置对象
- [unity菜鸟] 修改发布成web后的logo
- Debugging to Understand Finalizer--reference
- 从一个PHP数据生成 CSV 文件
- DICOM医学图像处理:DCMTK在VS2012中的配置
- DDOS学习笔记(《破坏之王-DDOS攻击与防范深度剖析》)
- thinkphp3.2.3使用ajax 的一些坑——使用AjaxReturn()后,直接返回null,模板文件不起作用
- 第5章 简单的C程序设计——循环结构程序设计
- 【BZOJ5492】[HNOI2019]校园旅行(bfs)
- Linux第一节课学习笔记
- bzoj4556(sam)
- Html5游戏框架createJs组件--EaselJS(二)绘图类graphics