首页 > 其他分享 >Heavy Transportation

Heavy Transportation

时间:2024-07-25 16:33:01浏览次数:13  
标签:Heavy 同学 Transportation int 穿梭 能量 include 星球

30世纪,X同学领悟了通天大道,开始在各个星球之间穿梭。但因为每次穿梭需要消耗巨大的能量,X同学只好暂时放弃了宇宙遨游的梦想。10年后,他发现每个星球之间的穿梭通道其实隐含着巨大的能量可供飞行,由于X同学天赋异禀,顿悟了吸星大法,他很快踏上了他的宇宙之旅。

X同学从地球(1号星球)出发,准备前往遥远的n号星球。因为有强大的力量束缚X同学的能力,X同学只能见到n个星球(1号到n号),且只能在他能力范围内的m个穿梭通道内通行,并用他顿悟的吸星大法吸取其中的全部或部分能量。两个星球之间有且只有一个穿梭通道。

由于穿梭通道的能量能给X同学带来难以言喻的爽快感,X同学希望自己在能到达n号星球的所有穿梭通道内,每次获得的能量尽可能大。遗憾的是,吸星大法是很容易走火入魔的。如果X同学在路途中的某一个通道内获得过大的能量,且在接下来的路途中,有通道无法提供与之相等的能量,X同学将倍感空虚,进而损伤道基,这显然是不能被X同学所接受的。当然,X同学也不会选择吸收大于前面任何通道吸收的能量,这将可能导致他爆体而亡。换句话说,X同学每次吸收的能量全部相同。所以,X同学必须提前做好功课,确定好每次能获得的最大能量。

Input

题目有多组测试数据。

第一行给一个 T

每一组数据的第一行给两个数n和m,表示X同学能见的n个星球和能通行的m个穿梭通道。
(1 <= n <= 1000)

接下来m行,每行三个数s1,s2,d代表两个星球的编号和它们之间穿梭通道隐含的全部能量。
(1 <= s1,s2 <= n , 1 <= d <= 1e6)

Output

每组数据先输出一行 Scenario #k,其中 k 是组别编号(从 1 开始)。

下一行输出一个整数,表示X同学每次能获得的最大能量。

最后输出一个空行。

Sample Input

1
3 3
1 2 3
1 3 4
2 3 5

Sample Output

Scenario #1:
4

思路 1

通过dijkstra,利用优先队列因为本题是求最大化到达终点路径中能吸收的最小能量,所以优先队列就用它默认的大顶堆即可,将dis[i]放入第一个值,顶点编号放入第二个值,

code 1

#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
const int N = 1e3 +5;
const int limit = 1e6 + 5;
int dis[N];//最大化到达终点路径中能吸收的最小能量
bool vis[N];
int n, m;
int e[N][N];
void dijkstra(){
    for (int i = 0; i <= n; ++i) {
        dis[i] = -limit;
        vis[i] = false;
    }
    int num = 0;
    priority_queue<pii> pq;//第一个存dis  第二个值存点
    dis[1] = limit;
    pq.push(pii(limit, 1));
    while(pq.size() && num <= n){
        int u = pq.top().second;
        pq.pop();//在top完 立马pop避免出现死循环
        if(vis[u]) continue;
        vis[u] = true;
        num++;
        for (int i = 1; i <= n; ++i) {
            if(e[u][i] != -1 && !vis[i]){
                dis[i] = max(dis[i], min(dis[u], e[u][i]));
                pq.push(pii(dis[i], i));
            }
        }
    }
}
int main() {
    int t;
    cin >> t;
    int k = 0;
    while(t--){
        cin >> n >> m;
        for (int i = 0; i < N - 1; ++i) 
            for (int j = i + 1; j < N; ++j) 
                e[i][j] = e[j][i] = -1;
            
        for (int i = 1; i <= m; ++i) {
            int x, y, d;
            cin >> x >> y >> d;
            e[x][y] = e[y][x] = d;
        }
        dijkstra();
        printf("Scenario #%d:\n", ++k);
        printf("%d\n\n", dis[n]);
    }
    return 0;
}

思路 2

Edge重载了<运算符,规定权值较大的边比较小,而sort函数是默认从小到大排 sort之后边的顺序其实是按权值从大到小

利用最大生成树保证生成 最小边权值最大的那一条路径,因为生成过程中,边的权值顺序是从大到小的,所以能使从结点1至结点n连通的最后一条边就是题目所求的最小边 只要结点1到结点n有通路就可以跳出,不要生成整棵树。

code 2

//
// Created by 33744 on 2024/7/25.
//
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e3 +5;
const int M = 5e5;
struct Edge{
    int from;
    int to;
    int d;
    //对edge排序 重载
    bool operator < (const Edge& t)const{
        return d > t.d;
    }
}edge[M];
int pre[N];
int find(int x){
    return pre[x] == x ? x : pre[x] = find(pre[x]);
}
int main() {
#ifdef ACM_LOCAL
    freopen("data.in", "r", stdin);
    freopen("data.out", "w", stdout);
#endif
    int t;
    cin >> t;
    int k = 0;
    while(t--){
        int n, m;
        scanf("%d%d",&n,&m);
        for (int i = 0; i <= n; ++i) {
            pre[i] = i;
        }

        for (int i = 1; i <= m; ++i) {
            int x, y;
            int d;
            scanf("%d%d%d",&x,&y,&d);
            edge[i].from = x;
            edge[i].to = y;
            edge[i].d = d;
        }
        //对edge里的d实现升序排序
        sort(edge + 1, edge + 1 + m);
        int ans = 0;
        for (int i = 1; i <= m; ++i) {
            Edge &e = edge[i];
            int x = find(e.from);
            int y = find(e.to);
            if(find(1) != find(n)){//1号星球和n号星球未联通
                ans = e.d;
                pre[x] = y;
            }
            else{
                break;//找到直接退出
            }
        }
        printf("Scenario #%d:\n", ++k);
        printf("%d\n\n", ans);

    }
    return 0;
}


标签:Heavy,同学,Transportation,int,穿梭,能量,include,星球
From: https://www.cnblogs.com/6Luffy6/p/18323481

相关文章

  • CF1909C Heavy Intervals 题解
    一种似乎更快抽象的解法?题面正文看这道题,给定序列\(l,r,c\),要求重构\(l,r,c\)使得\(\sum_{i=1}^n(r_i-l_i)\timesc_i\)最小。首先可以想到的就是尽量让小的\(r_i-l_i\)乘上大的\(c_i\)。这样子看来\(c_i\)几乎不需要更多的处理,仅需从小到大(或从大到小)排个序。来......
  • P10296 [CCC 2024 S2] Heavy-Light Composition 题解
    思路先扫一遍,计算每个字母出现的数量,然后判断是否是交替出现。代码#include<bits/stdc++.h>usingnamespacestd;intmain(){ intT,n; cin>>T>>n; while(T--){ intt[105]={0}; strings; cin>>s; for(inti=0;i<n;i++)t[s[i]-'a&#......
  • C. Heavy Intervals
    C.HeavyIntervalsYouhave$n$intervals$[l_1,r_1],[l_2,r_2],\dots,[l_n,r_n]$,suchthat$l_i<r_i$foreach$i$,andalltheendpointsoftheintervalsaredistinct.The$i$-thintervalhasweight$c_i$perunitlength.Therefore,theweight......
  • Soil pollution--Measures to control soil polluted by heavy metals
    Onespecificmeasure:strengthenpreventionandcontrolofsoilpollutionatitssource(fromOpinionsoftheCPCCentralCommitteeandTheStateCouncilonDeepeningtheBattleagainstPollution)Thedocumentrequiredthateffortswillbemadetoprevent......
  • SP16113 SUBTLEBA - Trucks Transportation 题解
    题目传送门前言本题样例有问题,如果想要样例可以去vjudge上。本题提交后可能会出现UKE,建议前往link提交,而且本篇题解中所提供的代码也为link代码。前置知识Kruskal重构树|最近公共祖先简化题意给定一个\(N\)个点\(M\)条边的有向图,共有\(S\)次询问,每次询问......
  • Best Heavy Duty Truck Diagnostic Software Of 2023 Completed List
    Diagnostictoolsareessentialintheautomotiveindustryforidentifyingandresolvingissueswithvehicles.Thesetoolsprovidetechnicianswiththenecessaryinformationtodiagnoseandrepairproblemsefficiently.Inthisarticle,wewillexplorethe......
  • R语言HAR和HEAVY模型分析高频金融数据波动率|附代码数据
    全文链接:http://tecdat.cn/?p=19129最近我们被客户要求撰写关于HAR和HEAVY模型的研究报告,包括一些图形和统计输出。在本文中,在学术界和金融界,分析高频财务数据的经济价值现在显而易见。摘要它是每日风险监控和预测的基础,也是高频交易的基础。为了在财务决策中高效利用高频数据......
  • POJ 1797 Heavy Transportation(迪杰斯特拉最短路变形)
    传送门题意分析:Hugo想要扩展他的公司,他有起重机要到目的地,到达目的地有很多条路径,但是,每一条路都有相应承重量,现在需要找出到达目的地的最大承重道路的承重质量。解题分析:首先,每一条路径的承重量取决于承重量最小的那条道路(短板效应),所以就是找所有路径的最小值,然后选择最小值最大的......
  • abc270_f Transportation 题解
    Transportation题意有\(n\)个城市,你可以执行以下操作若干次:选择一个没有建机场的城市\(i\),花费\(x_i\)建一个机场。选择一个没有建港口的城市\(i\),花费\(y_i\)建一个港口。还有\(m\)条没有修建的道路,第\(i\)条道路双向连接\(a_i\)和\(b_i\),修建这条道路需要......
  • ARC111C Too Heavy 题解
    无解的情况:当且仅当一个人手上的物品不是自己的物品,并且这个物品的质量大于自己的体重,这个不是自己的东西就卡手了,换不出去,无解。甲手上是乙的物品。乙的手上是丙的物品,丙......