首页 > 其他分享 >【题解】A18537.我心中珍藏的游戏

【题解】A18537.我心中珍藏的游戏

时间:2024-03-18 09:12:31浏览次数:27  
标签:cnt return int 题解 珍藏 edge edges A18537 技能

题目跳转

思路:

题目问最多可以获得的额外伤害,其实就是询问在这些技能中,如何怎样选取一个最优的发动技能顺序使得攻击加成最大。我们可以把每一个技能看作成一个图的顶点,把每一个攻击加成看作图的边,权制为\(Ei,j\)。由于\(Ei,j\)与\(Ej,i\)相等,则可以将这个图视为无向图。 可以样样例抽象成下图:

3
0 3 5
3 0 10
5 10 0

图片

考虑使用贪心的思想来解决本题,每次在图中找到权值最大的一条边选择即可,但图中不能出现环。因为是无向图,在考虑的时候可以忽略技能使用的顺序。接下来就是找一个最大生成树即可。

时间复杂度分析:本道题可以使用最小生成树Kruskal算法来实现,将题目的模型抽象化后可以被看作为一个最多有\(\frac{(1+n)*n}{2} - n\)条边的无向图(化简后可得\(\frac{n^2 - n}{2}\))。注意一开始需要对每一条边进行排序。本道题的时间复杂度约为\(O(2\times n^2 \log_2{n})\)。

参考代码:

#include <iostream>
#include <algorithm>
using namespace std;

int n, cnt, ans;
int f[805];
struct edge{
    int x, y, z;
} edges[700005];

bool cmp(edge a, edge b){
    return a.z > b.z;
}

int getf(int x){
    if (f[x] == x) return x;
    return f[x] = getf(f[x]);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n;
    for (int i=1; i<=n; i++){
        f[i] = i;
        for (int j=1; j<=n; j++){
            int t; cin >> t;
            if (i == j || t == 0) continue;
            edges[++cnt] = (edge){i, j, t};
        }
    }
    sort(edges+1, edges+1+cnt, cmp);
    for (int i=1; i<=cnt; i++){
        int u = edges[i].x;
        int v = edges[i].y;
        int U = getf(u), V = getf(v);
        if (U != V){
            f[U] = V;
            ans += edges[i].z;
        }
    }
    cout << ans << endl;
    return 0;
}

标签:cnt,return,int,题解,珍藏,edge,edges,A18537,技能
From: https://www.cnblogs.com/Macw07/p/18079613

相关文章

  • 【题解】P2627 [USACO11OPEN] Mowing the Lawn G
    【题解】P2627[USACO11OPEN]MowingtheLawnG题目跳转数据量比较大,暴力肯定是不行的。只能考虑用动态规划的方式来做。这道题有许多dp设计的思路,这里提供两个:方法一:普通状态设计定义\(dp[i][1/0]\)表示截止遍历到第\(i\)个元素时,选择第\(i\)个元素或不选第\(i\)个元素可以......
  • cfRound933div3-E题解
    E-RudolfandkBridges题意:选择的桥在连续的行中,每个桥的支架安装位置是可以不一样的.做法:赛时也感觉也感觉是dp,但是害怕dp,就选择了逃避.往贪心方向想,认为每次到了每个跳板都要跳到最远距离,实际上这样是不行的.很明显,可能存在近一点的点花费更少。实际上是dp,而且也不......
  • [ABC258F] Main Street 题解
    题意:你要在平面直角坐标系中行走,每一步可以上下左右四个方向任意移动$1$,耗时$k$秒。特别地,存在若干条快速通道,若该步起点和终点均满足$x\equiv0\pmod{B}$或$y\equiv0\pmod{B}$,则认为该步是在快速通道上进行,仅需耗时$1$秒。询问从$(S_x,S_y)$到$(G_x,G_y)$最......
  • P3939 数颜色 题解
    题目链接:数颜色经典题目了,暴力数据结构随便过,不过这种不带修的单个颜色的数量查找有个经典的做法:分桶+二分。具体的为每个颜色分桶,记录有序下标,这样就可以二分出\([l,r]\)上的下标个数。对于一次交换来说,如果相邻的颜色相同那么并不会发生交换,如果不同那么就发生交换,由于下标在......
  • P10218 [省选联考 2024] 魔法手杖 题解
    Description给定\(a_1,a_2,\dots,a_n\)以及\(b_1,b_2,\dots,b_n\),满足\(a_i\in[0,2^k-1]\)以及\(b_i\geq0\),你需要给出\(S\subseteq\{1,2,\dots,n\}\)以及\(x\in[0,2^k-1]\)满足以下条件:\(\sum\limits_{i\inS}b_i\leqm\);满足以上条件的前提下,最大化\......
  • P2746 [USACO5.3] 校园网Network of Schools 题解
    题目链接:校园网NetworkofSchools这个题得翻译下题目意思才知道在干嘛,题目一开始表明了这个是一个有向图,因为边是单向的。其次关于第一个问题:基于一个事实,如果有\(x\rightarrowy\rightarrowz\),那么只需要\(x\)接受协议,它所在的\(scc\)强连通分量上的点一定都能不需要......
  • AT_abc345_c [ABC345C] One Time Swap 题解
    题目传送门解法对于\(S_{i}\),设\(num_{S_{i}}\)表示\(S_{i+1\simn}\)中\(S_{i}\)出现的次数,则\(S_{i}\)对答案产生的贡献为\(n-i-num_{S_{i}}\)。注意原串在存在两个相同的元素的时候,也要统计在内。代码#include<bits/stdc++.h>usingnamespacestd;#definell......
  • P2163 [SHOI2007] 园丁的烦恼 题解
    题目链接:园丁的烦恼挺经典的题目,转化成二维数点去做这玩意和常规的偏序计数问题有区别:转化为求\(a\lex\leb\\&\&\c\ley\led\)的数量,这种就别想着拆来拆去了,这种权值类带偏序计数类问题,是经典的可差性问题,我们计:\(ans(x,l,r)\)表示\(t\lex,l\ley\ler\)的数......
  • P3302 [SDOI2013] 森林 题解
    题目链接:森林有意思的树上可持久化线段树变形题,建议先看这个:P2633Countonatree题解对于本题而言,我们重新阐述树上可持久化线段树的核心思想,对于点路径/边路径上的第\(k\)大问题,我们使用树上前缀和问题的思想,将其转化为可差性问题:一条路径上的权值线段树可以拆分为几棵权......
  • 贪心算法题解
    前言大家好,我是jiantaoyab,这篇文章将给大家介绍贪心算法和贪心算法题目的练习和解析,贪心算法的本质就是每一个阶段都是局部最优,从而实现全局最优。我们在做题的同时,不仅要把题目做出来,还要有严格的证明。柠檬水找零在柠檬水摊上,每一杯柠檬水的售价为5美元。顾客排队......