《第二次上机实验》解题报告

• 第1题  图的深度优先搜索I

先讲一下我在考试时的想法吧：当时还是不会用vector建立邻接边表，打算先用快排对边表排序，再记录以各个节点为起点的边表的位置，可是一旦用了快排稳定性就被破坏了，导致只有第四个点能过。于是回去后自学了vector。

思想；先用vector建立邻接边表，然后使用dfs，同时使用一个数组作为时间戳，用个数组保存经过的边，再用个数组保存一下各个点的发现时间和结束时间。最后用一个快排对保存的边进行排序，输出。

时间复杂度；O（n*log n）

总结；太离谱了，之前的dfs的题目都是要求从最小的点继续递归的，这回要求按输入顺序递归直接把我干蒙了（快排不稳定）。还好我已经基本会用vector了，下次就不会无从下手了。

#include<stdio.h>
#include<string.h>
#include<vector>
using namespace std;
int x[200100][2];
int t[100100][2] = {};
int n, m, i = 0, j = 1;
int y[200100][2];
vector<int>z[100100];
void gx(int a)
{
    i++;
    t[a][0] = i;
    int b, c, d;
    for (b =0;z[a].size()>b ; b++)
    {
        if (t[z[a][b]][0] == 0)
        {
            y[j][0] = a;
            y[j][1] = z[a][b];
            j++;
            gx(z[a][b]);
        }
    }
    i++;
    t[a][1] = i;
}
void fx(int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, a = y[l][1], t;
    while (j > i) {
        do i++; while (a > y[i][1]);
        do j--; while (a < y[j][1]);
        if (i < j)
        {
            t = y[i][1];
            y[i][1] = y[j][1];
            y[j][1] = t;
            t = y[i][0];
            y[i][0] = y[j][0];
            y[j][0] = t;
        }
    }
    fx(l, j);
    fx(j + 1, r);
}
int main(void)
{
    int a, b, c;
    scanf("%d %d", &n, &m);
    for (a = 1; a <= 2 * m; a += 2)
    {
        scanf("%d %d", &x[a][0], &x[a][1]);
        x[a + 1][0] = x[a][1];
        x[a + 1][1] = x[a][0];
    }
    for (a = 1; a <= 2 * m; a++)
    {
        z[x[a][0]].push_back(x[a][1]);
    }
    for (a = 1; a <= n; a++)
    {
        if (t[a][0] == 0)
        {
            gx(a);
        }
    }
    fx(1, j - 1);
    for (a = 1; a <= n; a++)
    {
        printf("%d %d\n", t[a][0], t[a][1]);
    }
    printf("%d\n", j - 1);
    for (a = 1; a <= j - 1; a++)
    {
        printf("%d %d\n", y[a][0], y[a][1]);
    }
    return 0;
}

• 第2题  二叉树最短路径长度

之前在洛谷做过一次，那次没真的建树，纯用递归写的，还好我还记得，于是复现了一下。

思想；先把先根遍历与后跟遍历输入两个数组里。调用我的函数，先跟序列的第一个为根，从中根遍历中找到先跟的第一个（根），把数组分为左右，再次递归，途中给他们加权。-----（注意，左递归要加一个“深度”，因为根被剔除了）

最后输出就行了。

时间复杂度；O（n）；

总结；用了一下我自己的算法，当中那个深度我即使知道也调试了很久，只能说有利有弊吧。

#include<stdio.h>
int x[20010][2];
int y[20010];
int z[20010];
void fx(int l, int r,int d)
{
    int a, b, c;
    if (l >= r)
        return;
    for (a = 1; a <= r; a++)
    {
        if (x[a][1] == x[l][0])
            break;
    }
    a += d;
    z[x[l + 1][0]] = z[x[l][0]] + y[x[l + 1][0]];
    fx(l+1, a,d+1);
    z[x[a + 1][0]] = z[x[l][0]] + y[x[a + 1][0]];
    fx(a + 1, r,d);
}
int main()
{
    int n,a,b,c;
    scanf("%d", &n);
    for (a = 1; a <= n; a++)
    {
        scanf("%d", &x[a][0]);
    }
    for (a = 1; a <= n; a++)
    {
        scanf("%d", &x[a][1]);
    }
    for (a = 1; a <= n; a++)
    {
        scanf("%d", &y[a]);
    }
    z[1] = y[1];
    fx(1, n,0);
    for (a = 1; a < n; a++)
    {
        printf("%d ", z[a]);
    }
    printf("%d", z[a]);
    return 0;
}
 

• 第3题  供电

最小生成树问题，考试的时候真的没想法，无从下手。在听孔神讲解时才知道可以引入虚节点。大开眼界。

思想；用的克鲁斯卡尔kruskal算法，先输入边，与虚边，用快排对权值进行排序，遍历有序（从小到大）边表，用并查集判环（等价类内部不连线），最后输出就行了。

时间复杂度；O（n*log n）

总结；引入虚节点是在拓扑排序时用到的，没想到最小生成树也能用，真是大开眼界。我用并查集优化判环算法（主要是不会）应该是正确的。

#include<stdio.h>
int x[60010][3];
int y[10010] = {};
int z[10010] = {};
void fx(int l, int r) {
    if (l >= r) return;
    int i = l - 1, j = r + 1, a = x[l + r >> 1][2], t;
    while (j > i) {
        do i++; while (a > x[i][2]);
        do j--; while (a < x[j][2]);
        if (i < j)
        {
            t = x[i][0];
            x[i][0] = x[j][0];
            x[j][0] = t;
            t = x[i][1];
            x[i][1] = x[j][1];
            x[j][1] = t;
            t = x[i][2];
            x[i][2] = x[j][2];
            x[j][2] = t;
        }
    }
    fx(l, j);
    fx(j + 1, r);
}
int find(int n)
{
    if (y[n] == n)
        return n;
    return y[n] = find(y[n]);
}
int main()
{
    int n, m, a, b, c,t=0;
    long long s = 0;
    scanf("%d %d", &n, &m);
    y[0] = 99999999;
    for (a = 1; a <= n; a++)
    {
        scanf("%d", &y[a]);
        x[a][0] = 0;
        x[a][1] = a;
        x[a][2] = y[a];
    }
    for (a = n+1; a <= m+n; a++)
    {
        scanf("%d %d %d", &x[a][0], &x[a][1], &x[a][2]);
    }
    fx(1, m+n);
    for (a = 0; a <= n; a++)
    {
        y[a] = a;
    }
    for (a = 1; a <= m+n; a++)
    {
        b = find(x[a][0]);
        c = find(x[a][1]);
        if (b != c)
        {
            y[c] = b;
            z[x[a][0]] = 1;
            z[x[a][1]] = 1;
            s += x[a][2];
        }
    }
    printf("%lld", s);
    return 0;
}

• 第4题  幸福指数

在考试的时候想骗一点分，没想到是一点都骗不到呀（悲）。

思想；先从前到后，维护一个单调队列，记录每个节点左边第一个比他小的数字位置，再从右面从后到前，维护一个单调队列，记录每个节点右边第一个比他小的数字位置。再从前到后，一次以每一个点为最小点，再查之前打好的表（两个单调队列记录的位置）算出每个点的最大幸福指数，最后输出最大的。

时间复杂度；O（n*log n）

总结；在课上听到了要以每一个点为最小值计算幸福指数。课后实现时用顺序查找为n*n的时间级的，最后一个点死活过不去，问了吴博睿，知道使用单调栈，但我不知到从后往前的单调栈如何维护，最后看了csdn才恍然大悟，打表！！！！

#include<stdio.h>
long long x[100100];
long long y[100100];
long long z[100100][2];
long long w[100100][2];
int main()
{
    long long n, a, b=0, c,d,t,i=0,j=0,k=0;
    long long s = 0;
    scanf("%lld", &n);
    for (a = 1; a <= n; a++)
    {
        scanf("%lld", &x[a]);
    }
    for (a = 1; a <= n; a++)
    {
        b += x[a];
        y[a] = b;
    }
    t = 1;
    w[0][0] = -1;
    for (a = 1; a <= n; a++)
    {
        while(x[a] <= w[t-1][0])
        {
            t--;
            w[t][0] = 0;
            w[t][1] = 0;
        }
        w[t][0] = x[a];
        w[t][1] = a;
        z[a][0] = w[t - 1][1];
        t++;
    }
    t = 1;
    for (a = 1; a <= n; a++)
    {
        w[a][0] = 0;
        w[a][1] = 0;
    }
    for (a = n; a >= 1; a--)
    {
        while (x[a] <= w[t - 1][0])
        {
            t--;
            w[t][0] = 0;
            w[t][1] = 0;
        }
        w[t][0] = x[a];
        w[t][1] = a;
        z[a][1] = w[t - 1][1];
        if (z[a][1] == 0)
            z[a][1] = n+1;
        t++;
    }
    for (b = 1; b <= n; b++)
    {
        d = z[b][0];
        c = z[b][1];
        t = y[c - 1] - y[d];
        if (x[b] * t > s||(x[b]*t==s&&c-d-2>k))
        {
            s = x[b] * t;
            i = d + 1;
            j = c - 1;
            k = j - i;
        }
    }
    printf("%lld\n",s);
    printf("%lld %lld", i, j);
    return 0;
}

 

• 第5题  联谊活动

二分图的最大匹配问题，即使听了孔姐姐的讲的还是写不来（我的问题），回去后查了csdn，基本是照着抄的写出来的。

思想；先输入二分图的边，遍历找边，若重复则递归找交叉边。一个数组记录这次是否被找到，一个数组记录右面对应的左点。

时间复杂度；O（n*n）

总结；注意最后要输入s*2，之前3—》4与4—》3是同一条边，不带权值，

#include<stdio.h>
#include<vector>
using namespace std;
vector<int>x[5100];
int y[5100] = {};
int z[5100] = {};
int n, m;
int fx(int a)
{
    int b, c, d;
    for (b = 0; b < x[a].size(); b++)
    {
        if (z[x[a][b]] == 0)
        {
            z[x[a][b]] = 1;
            if (fx(y[x[a][b]]) == 1 || y[x[a][b]] == 0)
            {
                y[x[a][b]] = a;
                return 1;
            }
        }

    }
    return 0;
}
int main()
{
    int e, a, b, c, t, s = 0;
    scanf("%d %d %d", &n, &m, &e);
    for (a = 1; a <= e; a++)
    {
        scanf("%d %d", &b, &c);
        if (b < c)
            x[b].push_back(c);
        else
        {
            x[c].push_back(b);
        }
    }
    for (a = 1; a <= n; a++)
    {
        for (b = n; b <= n+m; b++)
            z[b] = 0;
        if (fx(a) == 1)
            s++;
    }
    printf("%d", s * 2);
    return 0;
}