本文共 3067 字，大约阅读时间需要 10 分钟。
就按照区间那个理解,把并查集和克鲁斯卡尔算法都理解一下就可以了 ***************** 问题导入 对于一串数字如何求他的连续递增子序列使得整个序列和最大?(应该是这个意思,,没说错) 比如,随便给你一串儿数字 1 ,5 -4,-6 5 (1)最开始最通俗易懂也是最好想到的方法就是暴力 最基本的暴力方法是需要三个for循环 枚举左边端点l 右边端点r 里面是和 所有都算一次,那么需要0(n^3)的复杂度,如果是对于1e6的话是完全不够的 (2)我们可以尝试基本的简化来降低一点点复杂度: 预先算出Si=a1+...ai(类似打表) (这也是O(n)的复杂度,但是写在三重for循环之外,并不影响整体 那么,只要计算 Sr- S l-1即可(保证l<=r) (为什么是l-1呢?可以看做是一个大区间,想要得到l-r的值,用后面一直到r的减去前面l-1的,就是中间的(从l开始,一直到r的区间,得到区间就可以得到区间的和了,有了和存储一下就很方便枚举记录啦!)) (3)我们还可以进行进一步的化简 使用一个set: set<int>h 首先来明确一下目的,我们是想要找到max{Sr -S l-1} 也就是.. 可以直接枚举一边儿啊,Sr都取一下,找到每一个r对应的最小的l-r,就可以使得整个式子取得最大值了 对于每一个r,都去找一下l-1那个最小值..... 而且而且!因为r相当于是上界,所以前面的l-1也不是很难找 而且而且而且而且!!!不仅是上界,还可以充当max{Sr -S l-1}里面的前面那个Sr,岂不是更好! (4)具体操作: 你看啊!! for(int i=1;i<=n;i++)(z这里的i其实是r,其实也就是上界 p=find min(S l-1) (实现的话,,,,如果用set插入的话,,,,直接int a=*h.begin()就可以了,其实也是迭代器,但是*的话可以直接用成这样) h.insert(S i-1) ans=max(ans,Si -p)(这里的Si是枚举出来的Sr,而p是在这个r的上界之内,最小的Sl-r,这样就可以保证ans是最大的那个了) set是O(logn)的..很好!.. (6)终极 .. O(n)的好方法 一下子就完了 直接记录一下ans....从第一个开始加,每一次的答案都塞到set里面去。 如果是正的那就加了塞进去,如果是负的那就减了塞进去,如果是负数的话那就置为0(很重要的哦!其实也是可以重新开始了) 最后找到最大的就可以了...... (应该是这样的吧?) (7)克鲁斯卡尔算法: Kruskal算法 https://www.cnblogs.com/yoke/p/6697013.html 理解了过程了...代码还没写过=.= 大概就是: (利用并查集) 先按照边权排序,对于边和边权,v u,如果加入了没形成环,就加入使得形成 连通图,如果加入了形成了环就扔掉不要了 直到所有的点都被连通了为止... 它依赖并查集来实现的: (不知道是不是所有的连通图都要这样实现....反正按照并查集嘛,如果你是在一个部落里的就会形成环,然后放弃这个决定/如果不是的话就把你俩连起来) ..真便利啊 ************* (8)上面是最小生成树 下面是苗条生成树 这个题目的意思是首先给定了你点的数量和边的数量 然后输入 让你找到 所有的连通的图里面,边权值最小的那个,(也就是 最大的减最小的 差最小的那个 就是最苗条的生成树) 那么做起来还需要一点小心思: (以下几行为参考:https://blog.csdn.net/qq_32866009/article/details/52694005) 中文题意：给出一个n（n<=100）结点的图，求苗条度（最大边减最小边的值）尽量小的生成树。 【分析】首先把边按权值从小到大排序。对于一个连续的边集区间[L,R]，如果这些边使得n个点全部连通，则一定存在一个苗条度不超过W[R]-W[L]的生成树（其中W[i]表示排序后第i条边的权值）。 从小到大枚举L，对于每个L，从小到大枚举R，同时用并查集将新进入[L,R]的边的两端的点合并成一个集合，与Kruskal算法一样。当所有点连通时停止枚举R,换下一个L（并且把R重置为L）继续枚举。 然后代码我是看的这一份: https://blog.csdn.net/u013509299/article/details/39403747 其实都理解完了也不复杂,有一点需要注意的: 它其实也是在枚举区间哦....对于[L R ]这里面... 如果还没跑完,就形成了连通的树了(n=cnt-1) 然后,可以继续跑只是按照边权进行了排序,然后从start开始往下枚举
(好了,我应该不太懂,评论区有待补充)#include#include #include #include #include #include #define N 105 #define inf 0x3f3f3f3f #define pi acos(-1.0) #define eps 10e-6 using namespace std;struct node{ int x, y, w;}s[N*N];//105* 105bool cmp(node a, node b){ return a.w < b.w;}int f[N];int find(int x){ return x == f[x] ? x : f[x] = find(f[x]);}//return x = f[x] ? x : f[x] = find(f[x]);int main(){ int n, m; while (scanf_s("%d%d", &n, &m) != EOF) { if (n == 0 && m == 0) break; int i; for (i = 0; i < m; i++) scanf_s("%d%d%d", &s[i].x, &s[i].y, &s[i].w); sort(s, s + m, cmp); //仅仅是按照w排序了而已 s[m].w = -1; int ans = inf; int start = 0; int end; while (start < m) { for (i = 0; i <= n; i++) f[i] = i; int cnt = 0; for (i = start; i < m; i++) { int xx = find(s[i].x); int yy = find(s[i].y); if (xx != yy) { cnt++; f[xx] = yy; } if (cnt == n - 1) break; } if (cnt == n - 1) ans = min(ans, s[i].w - s[start].w); else break; while (s[start].w == s[start + 1].w) start++; start++; } if (ans == inf) printf("-1\n"); else printf("%d\n", ans); } return 0;}