数据结构第六次实验报告

7-2 二叉树加权距离 (100 分)

二叉树结点间的一种加权距离定义为:上行方向的变数×3 +下行方向的边数×2 。上行方向是指由结点向根的方向,下行方向是指与由根向叶结点方向。 给定一棵二叉树T及两个结点u和v,试求u到v的加权距离。

输入格式:

第1行,1个整数N,表示二叉树的结点数,(1≤N≤100000)。

随后若干行,每行两个整数a和b,用空格分隔,表示结点a到结点b有一条边,a、b是结点的编号,1≤a、b≤N;根结点编号为1,边从根向叶结点方向。

最后1行,两个整数u和v,用空格分隔,表示所查询的两个结点的编号,1≤u、v≤N。

输出格式:

1行,1个整数,表示查询的加权距离。

 存好节点深度,再一步一步找父亲,父亲相同即停止。

类似于并查集做法,但是不是找到根节点,而是找到最小公共祖先。

数据结构第六次实验报告

#include <iostream>
//int lef[100010];
//int rit[100010];
int fa[100010];
int dep[100010];
using namespace std;
int main()
{
    int m;
    int a, b;
    cin >> m;
    for (int i = 1; i < m; i++) {
        cin >> a >> b;
        fa[b] = a;
       // if (!lef[a])  lef[a] = b;
        //else rit[a] = b;
        dep[b] = dep[a] + 1;
    }
    cin >> a >> b;
    int sum = 0;
    while (a != b) {
        if (dep[a] >= dep[b]) {
            sum += 3;
            a = fa[a];
        }
        else {
            sum += 2;
            b = fa[b];
        }
    }
    cout << sum;
}

 

7-3 修轻轨 (100 分)

长春市有n个交通枢纽,计划在1号枢纽到n号枢纽之间修建一条轻轨。轻轨由多段隧道组成,候选隧道有m段。每段候选隧道只能由一个公司施工,施工天数对各家公司一致。有n家施工公司,每家公司同时最多只能修建一条候选隧道。所有公司可以同时开始施工。请评估:修建这条轻轨最少要多少天。。

输入格式:

第1行,两个整数n和m,用空格分隔,分别表示交通枢纽的数量和候选隧道的数量,1 ≤ n ≤ 100000,1 ≤ m ≤ 200000。

第2行到第m+1行,每行三个整数a、b、c,用空格分隔,表示枢纽a和枢纽b之间可以修建一条双向隧道,施工时间为c天,1 ≤ a, b ≤ n,1 ≤ c ≤ 1000000。

输出格式:

输出一行,包含一个整数,表示最少施工天数。

克鲁斯卡尔法,n和1连通就停止了。

// 6.9.3.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<algorithm>
#define maxn 100010
int father[maxn]; // 储存i的father父节点 
int ans = 0;
int n, m;
struct eg {
    int a, b, c;
    bool operator <(struct eg& ttt)const {
        return c < ttt.c;
    }
}edge[200010];
void makeSet() {
    for (int i = 0; i < maxn; i++)
        father[i] = i;
}
int Find(int x) { // 迭代找根节点
    int root = x; // 根节点 
    while (root != father[root]) { // 寻找根节点 
        root = father[root];
    }
    while (x != root) {
        int tmp = father[x];
        father[x] = root; // 根节点赋值 
        x = tmp;
    }
    return root;
}
void Union(int x, int y) { // 将x所在的集合和y所在的集合整合起来形成一个
    int a, b;
    a = Find(x);
    b = Find(y);
    father[a] = b; // y连在x的根节点上 或father[b] = a为x连在y的根节点
}
void Kruskal() {
    ans = 0;
    int summ = 0;
    for (int i = 1; i <= m; i++) {
        if (Find(edge[i].a) != Find(edge[i].b)) {
            Union(edge[i].a, edge[i].b);
            ans = edge[i].c;
            summ++;
           /* if (summ == n - 1) {
               ans= edge[i].c;
                return;
            }*/
            if (Find(1) == Find(n)) {
                return;
         }
       }
    }
}
using namespace std;
int main()
{
    cin >>n >> m;
    int w, e, r;
    for (int i = 1; i <= m; i++) {
        cin >> w >> e >> r;
        edge[i] = { w,e,r };
    }
    for (int i = 1; i <= n; i++) {
        father[i] = i;
    }
    sort(&edge[1], &edge[m + 1]);
    Kruskal();
    cout << ans;
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件,或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来,若要再次打开此项目,请转到“文件”>“打开”>“项目”并选择 .sln 文件

 

 

小唐正在学习数据结构。他尝试应用数据结构理论处理数据。最近,他接到一个任务,要求维护一个动态数据表,并支持如下操作:

  1. 插入操作(I):从表的一端插入一个整数。

  2. 删除操作(D):从表的另一端删除一个整数。

  3. 取反操作(R):把当前表中的所有整数都变成相反数。

  4. 取最大值操作(M):取当前表中的最大值。

    如何高效实现这个动态数据结构呢?

输入格式:

第1行,包含1个整数M,代表操作的个数, 2≤M≤1000000。

第2到M+1行,每行包含1个操作。每个操作以一个字符开头,可以是I、D、R、M。如果是I操作,格式如下:I x, x代表插入的整数,-10000000≤x≤10000000。 。

输出格式:

若干行,每行1个整数,对应M操作的返回值。如果M和D操作时队列为空,忽略对应操作。

聪明的做法是保存翻转的flag,flag不同相应取最大值/最小值的相反数,输入数时也考虑输入的正负,最值暴力写就好了,还可以优化的地方就是保存上次去最值的区间,以及最值取到的位置来简化运算,不过这种优化会被特殊数据卡死,单调队列就挺好了,还利于维护,不过要自己写或者使用deque(我只知道有),因为要同时头取最值,尾部删值。

我偷懒了hhhhh。

#include <iostream>
#include<stdio.h>
#include<queue>
#pragma warning(disable : 4996)
int kk[1000010];
int max;
std::queue<int> dddd;
using namespace std;
int main()
{
	int maxi1=0,maxi2=0,m;
	int max;
	int top =  0;
	int end = 1;
	int hao = 0;
	char d;
	int flag = 0;
	scanf(" %d",&m);
	for (int i = 1; i <= m; i++) {
		scanf(" %c",&d);
		switch (d) {
		case 'I':
			int j;
			scanf(" %d",&j);
			if (!flag)kk[++top] = j;
			else kk[++top] = -j;
			break;
		case 'D':
			if(end<=top)
			end++;
			break;
		case 'R':
			flag^=1;
			break;
		case 'M':
			if (end <= top) {
				int b = end;
				if (!flag) {
					max = kk[end];
					if (maxi1 < end)
						while (b <= top) {
							if (max <= kk[b]) {
								max = kk[b];
								maxi1 = b;
							}
							b++;
						}
					else {
						b = maxi1;
						while (b <= top) {
							if (max <= kk[b]) {
								max = kk[b];
								maxi1 = b;
							}
							b++;
						}
					}
					dddd.push(max);
					break;
				}
				else {
					max = kk[end];
					if (maxi2 < end)
						while (b <= top) {
							if (max > kk[b]) {
								max = kk[b];
								maxi2 = b;
							}
							b++;
						}
					else {
						b = maxi2;
						while (b <= top) {
							if (max > kk[b]) {
								max = kk[b];
								maxi2 = b;
							}
							b++;
						}
					}
					dddd.push(-max);
					break;
				}
			}
				
		}

	}
	while (!dddd.empty()) {
		printf("%d\n", dddd.front());
		dddd.pop();
	}
}

 

上一篇:860.柠檬水找零


下一篇:【LeetCode】每日一题2021/11/09