【HDOJ1598】【枚举+最小生成树】
2024-08-28 11:48:18
http://acm.hdu.edu.cn/showproblem.php?pid=1598
find the most comfortable road
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8648 Accepted Submission(s): 3648
Problem Description
XX星有许多城市,城市之间通过一种奇怪的高速公路SARS(Super Air Roam Structure---超级空中漫游结构)进行交流,每条SARS都对行驶在上面的Flycar限制了固定的Speed,同时XX星人对 Flycar的“舒适度”有特殊要求,即乘坐过程中最高速度与最低速度的差越小乘坐越舒服 ,(理解为SARS的限速要求,flycar必须瞬间提速/降速,痛苦呀 ),
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的)。
但XX星人对时间却没那么多要求。要你找出一条城市间的最舒适的路径。(SARS是双向的)。
Input
输入包括多个测试实例,每个实例包括:
第一行有2个正整数n (1<n<=200)和m (m<=1000),表示有N个城市和M条SARS。
接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speedSARS。speed<=1000000
然后是一个正整数Q(Q<11),表示寻路的个数。
接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。
第一行有2个正整数n (1<n<=200)和m (m<=1000),表示有N个城市和M条SARS。
接下来的行是三个正整数StartCity,EndCity,speed,表示从表面上看StartCity到EndCity,限速为speedSARS。speed<=1000000
然后是一个正整数Q(Q<11),表示寻路的个数。
接下来Q行每行有2个正整数Start,End, 表示寻路的起终点。
Output
每个寻路要求打印一行,仅输出一个非负整数表示最佳路线的舒适度最高速与最低速的差。如果起点和终点不能到达,那么输出-1。
Sample Input
4 4
1 2 2
2 3 4
1 4 1
3 4 2
2
1 3
1 2
1 2 2
2 3 4
1 4 1
3 4 2
2
1 3
1 2
Sample Output
1
0
0
题目大意:就是【多组数据】给一个图,有Q次询问,询问从 顶点 S 到顶点 T 的路径中经过的边中最大值-最小值的最小值是多少,如果S和T不能连通就输出-1
题目分析:对边进行排序【即最小生成树的第一步】,枚举最小值,然后一点点生成树直到S与T连通,将导致S与T连通的那条边【也就是最大权值边】的权值-枚举的那个最小值来更新所求的最小值。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
struct edge{
int to;
int from;
int len;
}EDGE[];
int pre[];
int n,m;
bool cmp(struct edge qaq,struct edge qwq)
{
return qaq.len<qwq.len;
}
int find(int x)
{
int xx=x;
while(x!=pre[x])
{
x=pre[x];
}
while(pre[xx]!=x)
{
int t=pre[xx];
pre[xx]=x;
xx=t;
}
return x;
}
int main()
{
while(scanf("%d%d",&n,&m)==)
{ int mmax=;
int tot=;
// int mmin=1000005;
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
EDGE[tot].from=a;
EDGE[tot].to=b;
EDGE[tot++].len=c;
} sort(EDGE,EDGE+tot,cmp);
int orz;
scanf("%d",&orz);
while(orz--)
{
int mmin=-;
int orz1,orz2;
scanf("%d%d",&orz1,&orz2);
for(int i = ; i < tot ; i++)//枚举最小值
{
bool flag=false;
for(int j = ; j <= n ; j++)//复位父节点
pre[j]=j;
int wqw=EDGE[i].len;
int waw=EDGE[i].len;
pre[find(EDGE[i].from)]=find(EDGE[i].to);
for(int j = i+ ; j < tot ; j++)
{
if(find(orz1)==find(orz2))//如果已经连通就记录最大值并跳出
{
flag=true;
break;
}
else
{
pre[find(EDGE[j].from)]=find(EDGE[j].to);//更新所求的【最大权值-最小权值】的最小值
waw=EDGE[j].len;
}
}
if(flag){
if(mmin==-)mmin=waw-wqw;
mmin=min(waw-wqw,mmin);
}
else
{
break;
}
}
printf("%d\n",mmin);
}
}
return ;
}
最新文章
- 内存VSS/RSS/PSS/USS名词解释
- sizzle分析记录:getAttribute和getAttributeNode
- TYVJ P1069 cowtour 看不懂题意
- oracle 中的存储过程
- C++断言与静态断言
- IIS FTP文件服务器搭建步骤
- new的例子
- Linux系统(四)负载均衡LVS集群之NAT模式
- 01_ExtJS_HelloWorld
- ECS上nginx搭建反向代理通过内网访问阿里云OSS服务
- awk字符串操作(字符串链接、传入传出shell变量)
- git强制覆盖更新
- LeetCode 500 Keyboard Row 解题报告
- TensorFlow设置GPU占用量
- Chrome插件消息传递实例
- CentOS7 下更改源
- pbft流程深层分析和解释(转)
- 008 使用POJO对象绑定请求参数
- 【机器学习】Logistic Regression 的前世今生(理论篇)
- Shell与Bash